bond: New function bond_is_balanced().
[sliver-openvswitch.git] / lib / bond.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks.
3  *
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:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <config.h>
18
19 #include "bond.h"
20
21 #include <limits.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24
25 #include "coverage.h"
26 #include "dynamic-string.h"
27 #include "flow.h"
28 #include "hmap.h"
29 #include "lacp.h"
30 #include "list.h"
31 #include "netdev.h"
32 #include "odp-util.h"
33 #include "ofpbuf.h"
34 #include "packets.h"
35 #include "poll-loop.h"
36 #include "tag.h"
37 #include "timeval.h"
38 #include "unixctl.h"
39 #include "vlog.h"
40
41 VLOG_DEFINE_THIS_MODULE(bond);
42
43 COVERAGE_DEFINE(bond_process_lacp);
44
45 /* Bit-mask for hashing a flow down to a bucket.
46  * There are (BOND_MASK + 1) buckets. */
47 #define BOND_MASK 0xff
48
49 /* A hash bucket for mapping a flow to a slave.
50  * "struct bond" has an array of (BOND_MASK + 1) of these. */
51 struct bond_entry {
52     struct bond_slave *slave;   /* Assigned slave, NULL if unassigned. */
53     uint64_t tx_bytes;          /* Count of bytes recently transmitted. */
54     tag_type tag;               /* Tag for entry<->slave association. */
55     struct list list_node;      /* In bond_slave's 'entries' list. */
56 };
57
58 /* A bond slave, that is, one of the links comprising a bond. */
59 struct bond_slave {
60     struct hmap_node hmap_node; /* In struct bond's slaves hmap. */
61     struct bond *bond;          /* The bond that contains this slave. */
62     void *aux;                  /* Client-provided handle for this slave. */
63
64     struct netdev *netdev;      /* Network device, owned by the client. */
65     char *name;                 /* Name (a copy of netdev_get_name(netdev)). */
66
67     /* Link status. */
68     long long delay_expires;    /* Time after which 'enabled' may change. */
69     bool up;                    /* Last link status read from netdev. */
70     bool enabled;               /* May be chosen for flows? */
71     tag_type tag;               /* Tag associated with this slave. */
72
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. */
77 };
78
79 /* A bond, that is, a set of network devices grouped to improve performance or
80  * robustness.  */
81 struct bond {
82     struct hmap_node hmap_node; /* In 'all_bonds' hmap. */
83     char *name;                 /* Name provided by client. */
84
85     /* Slaves. */
86     struct hmap slaves;
87
88     /* Bonding info. */
89     enum bond_mode balance;     /* Balancing mode, one of BM_*. */
90     struct bond_slave *active_slave;
91     tag_type no_slaves_tag;     /* Tag for flows when all slaves disabled. */
92     int updelay, downdelay;     /* Delay before slave goes up/down, in ms. */
93
94     /* SLB specific bonding info. */
95     struct bond_entry *hash;     /* An array of (BOND_MASK + 1) elements. */
96     int rebalance_interval;      /* Interval between rebalances, in ms. */
97     long long int next_rebalance; /* Next rebalancing time. */
98     bool send_learning_packets;
99
100     /* LACP. */
101     struct lacp *lacp;          /* LACP object. NULL if LACP is disabled. */
102
103     /* Monitoring. */
104     enum bond_detect_mode detect;     /* Link status mode, one of BLSM_*. */
105     struct netdev_monitor *monitor;   /* detect == BLSM_CARRIER only. */
106     long long int miimon_interval;    /* Miimon status refresh interval. */
107     long long int miimon_next_update; /* Time of next miimon update. */
108
109     /* Legacy compatibility. */
110     long long int next_fake_iface_update; /* LLONG_MAX if disabled. */
111
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;
116 };
117
118 static struct hmap all_bonds = HMAP_INITIALIZER(&all_bonds);
119
120 static void bond_entry_reset(struct bond *);
121 static struct bond_slave *bond_slave_lookup(struct bond *, const void *slave_);
122 static bool bond_is_link_up(struct bond *, struct netdev *);
123 static void bond_enable_slave(struct bond_slave *, bool enable,
124                               struct tag_set *);
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);
130 static unsigned int bond_hash_tcp(const struct flow *, uint16_t vlan);
131 static struct bond_entry *lookup_bond_entry(const struct bond *,
132                                             const struct flow *,
133                                             uint16_t vlan);
134 static tag_type bond_get_active_slave_tag(const struct bond *);
135 static struct bond_slave *choose_output_slave(const struct bond *,
136                                               const struct flow *,
137                                               uint16_t vlan);
138 static void bond_update_fake_slave_stats(struct bond *);
139
140 /* Attempts to parse 's' as the name of a bond balancing mode.  If successful,
141  * stores the mode in '*balance' and returns true.  Otherwise returns false
142  * without modifying '*balance'. */
143 bool
144 bond_mode_from_string(enum bond_mode *balance, const char *s)
145 {
146     if (!strcmp(s, bond_mode_to_string(BM_TCP))) {
147         *balance = BM_TCP;
148     } else if (!strcmp(s, bond_mode_to_string(BM_SLB))) {
149         *balance = BM_SLB;
150     } else if (!strcmp(s, bond_mode_to_string(BM_AB))) {
151         *balance = BM_AB;
152     } else {
153         return false;
154     }
155     return true;
156 }
157
158 /* Returns a string representing 'balance'. */
159 const char *
160 bond_mode_to_string(enum bond_mode balance) {
161     switch (balance) {
162     case BM_TCP:
163         return "balance-tcp";
164     case BM_SLB:
165         return "balance-slb";
166     case BM_AB:
167         return "active-backup";
168     }
169     NOT_REACHED();
170 }
171
172 /* Attempts to parse 's' as the name of a bond link status detection mode.  If
173  * successful, stores the mode in '*detect' and returns true.  Otherwise
174  * returns false without modifying '*detect'. */
175 bool
176 bond_detect_mode_from_string(enum bond_detect_mode *detect, const char *s)
177 {
178     if (!strcmp(s, bond_detect_mode_to_string(BLSM_CARRIER))) {
179         *detect = BLSM_CARRIER;
180     } else if (!strcmp(s, bond_detect_mode_to_string(BLSM_MIIMON))) {
181         *detect = BLSM_MIIMON;
182     } else {
183         return false;
184     }
185     return true;
186 }
187
188 /* Returns a string representing 'detect'. */
189 const char *
190 bond_detect_mode_to_string(enum bond_detect_mode detect)
191 {
192     switch (detect) {
193     case BLSM_CARRIER:
194         return "carrier";
195     case BLSM_MIIMON:
196         return "miimon";
197     }
198     NOT_REACHED();
199 }
200 \f
201 /* Creates and returns a new bond whose configuration is initially taken from
202  * 's'.
203  *
204  * The caller should register each slave on the new bond by calling
205  * bond_slave_register().  */
206 struct bond *
207 bond_create(const struct bond_settings *s)
208 {
209     struct bond *bond;
210
211     bond = xzalloc(sizeof *bond);
212     hmap_init(&bond->slaves);
213     bond->no_slaves_tag = tag_create_random();
214     bond->miimon_next_update = LLONG_MAX;
215     bond->next_fake_iface_update = LLONG_MAX;
216
217     bond_reconfigure(bond, s);
218
219     tag_set_init(&bond->unixctl_tags);
220
221     return bond;
222 }
223
224 /* Frees 'bond'. */
225 void
226 bond_destroy(struct bond *bond)
227 {
228     struct bond_slave *slave, *next_slave;
229
230     if (!bond) {
231         return;
232     }
233
234     hmap_remove(&all_bonds, &bond->hmap_node);
235
236     HMAP_FOR_EACH_SAFE (slave, next_slave, hmap_node, &bond->slaves) {
237         hmap_remove(&bond->slaves, &slave->hmap_node);
238         /* Client owns 'slave->netdev'. */
239         free(slave->name);
240         free(slave);
241     }
242     hmap_destroy(&bond->slaves);
243
244     free(bond->hash);
245
246     lacp_destroy(bond->lacp);
247
248     netdev_monitor_destroy(bond->monitor);
249
250     free(bond->name);
251     free(bond);
252 }
253
254 /* Updates 'bond''s overall configuration to 's'.
255  *
256  * The caller should register each slave on 'bond' by calling
257  * bond_slave_register().  This is optional if none of the slaves'
258  * configuration has changed, except that it is mandatory if 's' enables LACP
259  * and 'bond' previously didn't have LACP enabled.  In any case it can't
260  * hurt.
261  *
262  * Returns true if the configuration has changed in such a way that requires
263  * flow revalidation.
264  * */
265 bool
266 bond_reconfigure(struct bond *bond, const struct bond_settings *s)
267 {
268     bool revalidate = false;
269
270     if (!bond->name || strcmp(bond->name, s->name)) {
271         if (bond->name) {
272             hmap_remove(&all_bonds, &bond->hmap_node);
273             free(bond->name);
274         }
275         bond->name = xstrdup(s->name);
276         hmap_insert(&all_bonds, &bond->hmap_node, hash_string(bond->name, 0));
277     }
278
279     bond->detect = s->detect;
280     bond->miimon_interval = s->miimon_interval;
281     bond->updelay = s->up_delay;
282     bond->downdelay = s->down_delay;
283     bond->rebalance_interval = s->rebalance_interval;
284
285     if (bond->balance != s->balance) {
286         bond->balance = s->balance;
287         revalidate = true;
288     }
289
290     if (bond->detect == BLSM_CARRIER) {
291         struct bond_slave *slave;
292
293         if (!bond->monitor) {
294             bond->monitor = netdev_monitor_create();
295         }
296
297         HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
298             netdev_monitor_add(bond->monitor, slave->netdev);
299         }
300     } else {
301         netdev_monitor_destroy(bond->monitor);
302         bond->monitor = NULL;
303
304         if (bond->miimon_next_update == LLONG_MAX) {
305             bond->miimon_next_update = time_msec() + bond->miimon_interval;
306         }
307     }
308
309     if (s->lacp) {
310         if (!bond->lacp) {
311             bond->lacp = lacp_create();
312         }
313         lacp_configure(bond->lacp, s->lacp);
314     } else {
315         lacp_destroy(bond->lacp);
316         bond->lacp = NULL;
317     }
318
319     if (s->fake_iface) {
320         if (bond->next_fake_iface_update == LLONG_MAX) {
321             bond->next_fake_iface_update = time_msec();
322         }
323     } else {
324         bond->next_fake_iface_update = LLONG_MAX;
325     }
326
327     if (bond->balance == BM_AB || !bond->hash || revalidate) {
328         bond_entry_reset(bond);
329     }
330
331     return revalidate;
332 }
333
334 /* Registers 'slave_' as a slave of 'bond'.  The 'slave_' pointer is an
335  * arbitrary client-provided pointer that uniquely identifies a slave within a
336  * bond.  If 'slave_' already exists within 'bond' then this function
337  * reconfigures the existing slave.
338  *
339  * 'netdev' must be the network device that 'slave_' represents.  It is owned
340  * by the client, so the client must not close it before either unregistering
341  * 'slave_' or destroying 'bond'.
342  *
343  * If 'bond' has a LACP configuration then 'lacp_settings' must point to LACP
344  * settings for 'slave_'; otherwise 'lacp_settings' is ignored.
345  */
346 void
347 bond_slave_register(struct bond *bond, void *slave_, struct netdev *netdev,
348                     const struct lacp_slave_settings *lacp_settings)
349 {
350     struct bond_slave *slave = bond_slave_lookup(bond, slave_);
351
352     if (!slave) {
353         slave = xzalloc(sizeof *slave);
354
355         hmap_insert(&bond->slaves, &slave->hmap_node, hash_pointer(slave_, 0));
356         slave->bond = bond;
357         slave->aux = slave_;
358         slave->delay_expires = LLONG_MAX;
359         slave->up = bond_is_link_up(bond, netdev);
360         slave->enabled = false;
361         bond_enable_slave(slave, slave->up, NULL);
362     }
363
364     slave->netdev = netdev;
365     free(slave->name);
366     slave->name = xstrdup(netdev_get_name(netdev));
367
368     if (bond->lacp) {
369         assert(lacp_settings != NULL);
370         lacp_slave_register(bond->lacp, slave, lacp_settings);
371     }
372 }
373
374 /* Unregisters 'slave_' from 'bond'.  If 'bond' does not contain such a slave
375  * then this function has no effect.
376  *
377  * Unregistering a slave invalidates all flows. */
378 void
379 bond_slave_unregister(struct bond *bond, const void *slave_)
380 {
381     struct bond_slave *slave = bond_slave_lookup(bond, slave_);
382     bool del_active;
383
384     if (!slave) {
385         return;
386     }
387
388     bond_enable_slave(slave, false, NULL);
389
390     del_active = bond->active_slave == slave;
391     if (bond->hash) {
392         struct bond_entry *e;
393         for (e = bond->hash; e <= &bond->hash[BOND_MASK]; e++) {
394             if (e->slave == slave) {
395                 e->slave = NULL;
396             }
397         }
398     }
399
400     free(slave->name);
401
402     hmap_remove(&bond->slaves, &slave->hmap_node);
403     /* Client owns 'slave->netdev'. */
404     free(slave);
405
406     if (del_active) {
407         struct tag_set tags;
408
409         tag_set_init(&tags);
410         bond_choose_active_slave(bond, &tags);
411         bond->send_learning_packets = true;
412     }
413 }
414
415 /* Callback for lacp_run(). */
416 static void
417 bond_send_pdu_cb(void *slave_, const struct lacp_pdu *pdu)
418 {
419     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 10);
420     struct bond_slave *slave = slave_;
421     uint8_t ea[ETH_ADDR_LEN];
422     int error;
423
424     error = netdev_get_etheraddr(slave->netdev, ea);
425     if (!error) {
426         struct lacp_pdu *packet_pdu;
427         struct ofpbuf packet;
428
429         ofpbuf_init(&packet, 0);
430         packet_pdu = eth_compose(&packet, eth_addr_lacp, ea, ETH_TYPE_LACP,
431                                  sizeof *packet_pdu);
432         *packet_pdu = *pdu;
433         error = netdev_send(slave->netdev, &packet);
434         if (error) {
435             VLOG_WARN_RL(&rl, "bond %s: sending LACP PDU on slave %s failed "
436                          "(%s)",
437                          slave->bond->name, slave->name, strerror(error));
438         }
439         ofpbuf_uninit(&packet);
440     } else {
441         VLOG_ERR_RL(&rl, "bond %s: cannot obtain Ethernet address of slave "
442                     "%s (%s)",
443                     slave->bond->name, slave->name, strerror(error));
444     }
445 }
446
447 /* Performs periodic maintenance on 'bond'.  The caller must provide 'tags' to
448  * allow tagged flows to be invalidated.
449  *
450  * The caller should check bond_should_send_learning_packets() afterward. */
451 void
452 bond_run(struct bond *bond, struct tag_set *tags)
453 {
454     struct bond_slave *slave;
455     bool is_tcp_hash = bond_is_tcp_hash(bond);
456
457     /* Update link status. */
458     if (bond->detect == BLSM_CARRIER
459         || time_msec() >= bond->miimon_next_update)
460     {
461         HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
462             slave->up = bond_is_link_up(bond, slave->netdev);
463         }
464         bond->miimon_next_update = time_msec() + bond->miimon_interval;
465     }
466
467     /* Update LACP. */
468     if (bond->lacp) {
469         HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
470             lacp_slave_enable(bond->lacp, slave, slave->enabled);
471         }
472
473         lacp_run(bond->lacp, bond_send_pdu_cb);
474     }
475
476     /* Enable slaves based on link status and LACP feedback. */
477     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
478         bond_link_status_update(slave, tags);
479     }
480     if (!bond->active_slave || !bond->active_slave->enabled) {
481         bond_choose_active_slave(bond, tags);
482     }
483
484     /* Update fake bond interface stats. */
485     if (time_msec() >= bond->next_fake_iface_update) {
486         bond_update_fake_slave_stats(bond);
487         bond->next_fake_iface_update = time_msec() + 1000;
488     }
489
490     if (is_tcp_hash != bond_is_tcp_hash(bond)) {
491         struct bond_slave *slave;
492
493         bond_entry_reset(bond);
494         HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
495             tag_set_add(tags, slave->tag);
496         }
497     }
498
499     /* Invalidate any tags required by  */
500     tag_set_union(tags, &bond->unixctl_tags);
501     tag_set_init(&bond->unixctl_tags);
502 }
503
504 /* Causes poll_block() to wake up when 'bond' needs something to be done. */
505 void
506 bond_wait(struct bond *bond)
507 {
508     struct bond_slave *slave;
509
510     if (bond->detect == BLSM_CARRIER) {
511         netdev_monitor_poll_wait(bond->monitor);
512     } else {
513         poll_timer_wait_until(bond->miimon_next_update);
514     }
515
516     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
517         if (slave->delay_expires != LLONG_MAX) {
518             poll_timer_wait_until(slave->delay_expires);
519         }
520     }
521
522     if (bond->next_fake_iface_update != LLONG_MAX) {
523         poll_timer_wait_until(bond->next_fake_iface_update);
524     }
525
526     /* Ensure that any saved tags get revalidated right away. */
527     if (!tag_set_is_empty(&bond->unixctl_tags)) {
528         poll_immediate_wake();
529     }
530
531     /* We don't wait for bond->next_rebalance because rebalancing can only run
532      * at a flow account checkpoint.  ofproto does checkpointing on its own
533      * schedule and bond_rebalance() gets called afterward, so we'd just be
534      * waking up for no purpose. */
535 }
536 \f
537 /* MAC learning table interaction. */
538
539 static bool
540 may_send_learning_packets(const struct bond *bond)
541 {
542     return !lacp_negotiated(bond->lacp) && bond->balance != BM_AB;
543 }
544
545 /* Returns true if 'bond' needs the client to send out packets to assist with
546  * MAC learning on 'bond'.  If this function returns true, then the client
547  * should iterate through its MAC learning table for the bridge on which 'bond'
548  * is located.  For each MAC that has been learned on a port other than 'bond',
549  * it should call bond_send_learning_packet().
550  *
551  * This function will only return true if 'bond' is in SLB mode and LACP is not
552  * negotiated.  Otherwise sending learning packets isn't necessary.
553  *
554  * Calling this function resets the state that it checks. */
555 bool
556 bond_should_send_learning_packets(struct bond *bond)
557 {
558     bool send = bond->send_learning_packets && may_send_learning_packets(bond);
559     bond->send_learning_packets = false;
560     return send;
561 }
562
563 /* Sends a gratuitous learning packet on 'bond' from 'eth_src' on 'vlan'.
564  *
565  * See bond_should_send_learning_packets() for description of usage. */
566 int
567 bond_send_learning_packet(struct bond *bond,
568                           const uint8_t eth_src[ETH_ADDR_LEN],
569                           uint16_t vlan)
570 {
571     struct bond_slave *slave;
572     struct ofpbuf packet;
573     struct flow flow;
574     int error;
575
576     assert(may_send_learning_packets(bond));
577     if (!bond->active_slave) {
578         /* Nowhere to send the learning packet. */
579         return 0;
580     }
581
582     memset(&flow, 0, sizeof flow);
583     memcpy(flow.dl_src, eth_src, ETH_ADDR_LEN);
584     slave = choose_output_slave(bond, &flow, vlan);
585
586     ofpbuf_init(&packet, 0);
587     compose_benign_packet(&packet, "Open vSwitch Bond Failover", 0xf177,
588                           eth_src);
589     if (vlan) {
590         eth_set_vlan_tci(&packet, htons(vlan));
591     }
592     error = netdev_send(slave->netdev, &packet);
593     ofpbuf_uninit(&packet);
594
595     return error;
596 }
597 \f
598 /* Checks whether a packet that arrived on 'slave_' within 'bond', with an
599  * Ethernet destination address of 'eth_dst', should be admitted.
600  *
601  * The return value is one of the following:
602  *
603  *    - BV_ACCEPT: Admit the packet.
604  *
605  *    - BV_DROP: Drop the packet.
606  *
607  *    - BV_DROP_IF_MOVED: Consult the MAC learning table for the packet's
608  *      Ethernet source address and VLAN.  If there is none, or if the packet
609  *      is on the learned port, then admit the packet.  If a different port has
610  *      been learned, however, drop the packet (and do not use it for MAC
611  *      learning).
612  */
613 enum bond_verdict
614 bond_check_admissibility(struct bond *bond, const void *slave_,
615                          const uint8_t eth_dst[ETH_ADDR_LEN], tag_type *tags)
616 {
617     /* Admit all packets if LACP has been negotiated, because that means that
618      * the remote switch is aware of the bond and will "do the right thing". */
619     if (lacp_negotiated(bond->lacp)) {
620         return BV_ACCEPT;
621     }
622
623     /* Drop all multicast packets on inactive slaves. */
624     if (eth_addr_is_multicast(eth_dst)) {
625         *tags |= bond_get_active_slave_tag(bond);
626         if (bond->active_slave != bond_slave_lookup(bond, slave_)) {
627             return BV_DROP;
628         }
629     }
630
631     /* Drop all packets for which we have learned a different input port,
632      * because we probably sent the packet on one slave and got it back on the
633      * other.  Gratuitous ARP packets are an exception to this rule: the host
634      * has moved to another switch.  The exception to the exception is if we
635      * locked the learning table to avoid reflections on bond slaves. */
636     return BV_DROP_IF_MOVED;
637 }
638
639 /* Returns the slave (registered on 'bond' by bond_slave_register()) to which
640  * a packet with the given 'flow' and 'vlan' should be forwarded.  Returns
641  * NULL if the packet should be dropped because no slaves are enabled.
642  *
643  * 'vlan' is not necessarily the same as 'flow->vlan_tci'.  First, 'vlan'
644  * should be a VID only (i.e. excluding the PCP bits).  Second,
645  * 'flow->vlan_tci' is the VLAN TCI that appeared on the packet (so it will be
646  * nonzero only for trunk ports), whereas 'vlan' is the logical VLAN that the
647  * packet belongs to (so for an access port it will be the access port's VLAN).
648  *
649  * Adds a tag to '*tags' that associates the flow with the returned slave.
650  */
651 void *
652 bond_choose_output_slave(struct bond *bond, const struct flow *flow,
653                          uint16_t vlan, tag_type *tags)
654 {
655     struct bond_slave *slave = choose_output_slave(bond, flow, vlan);
656     if (slave) {
657         *tags |= slave->tag;
658         return slave->aux;
659     } else {
660         *tags |= bond->no_slaves_tag;
661         return NULL;
662     }
663 }
664
665 /* Processes LACP packet 'packet', which was received on 'slave_' within
666  * 'bond'.
667  *
668  * The client should use this function to pass along LACP messages received on
669  * any of 'bond''s slaves. */
670 void
671 bond_process_lacp(struct bond *bond, void *slave_, const struct ofpbuf *packet)
672 {
673     if (bond->lacp) {
674         struct bond_slave *slave = bond_slave_lookup(bond, slave_);
675         const struct lacp_pdu *pdu = parse_lacp_packet(packet);
676         if (slave && pdu) {
677             COVERAGE_INC(bond_process_lacp);
678             lacp_process_pdu(bond->lacp, slave, pdu);
679         }
680     }
681 }
682 \f
683 /* Rebalancing. */
684
685 static bool
686 bond_is_balanced(const struct bond *bond)
687 {
688     return bond->balance == BM_SLB || bond->balance == BM_TCP;
689 }
690
691 /* Notifies 'bond' that 'n_bytes' bytes were sent in 'flow' within 'vlan'. */
692 void
693 bond_account(struct bond *bond, const struct flow *flow, uint16_t vlan,
694              uint64_t n_bytes)
695 {
696
697     if (bond_is_balanced(bond)) {
698         lookup_bond_entry(bond, flow, vlan)->tx_bytes += n_bytes;
699     }
700 }
701
702 static struct bond_slave *
703 bond_slave_from_bal_node(struct list *bal)
704 {
705     return CONTAINER_OF(bal, struct bond_slave, bal_node);
706 }
707
708 static void
709 log_bals(struct bond *bond, const struct list *bals)
710 {
711     if (VLOG_IS_DBG_ENABLED()) {
712         struct ds ds = DS_EMPTY_INITIALIZER;
713         const struct bond_slave *slave;
714
715         LIST_FOR_EACH (slave, bal_node, bals) {
716             if (ds.length) {
717                 ds_put_char(&ds, ',');
718             }
719             ds_put_format(&ds, " %s %"PRIu64"kB",
720                           slave->name, slave->tx_bytes / 1024);
721
722             if (!slave->enabled) {
723                 ds_put_cstr(&ds, " (disabled)");
724             }
725             if (!list_is_empty(&slave->entries)) {
726                 struct bond_entry *e;
727
728                 ds_put_cstr(&ds, " (");
729                 LIST_FOR_EACH (e, list_node, &slave->entries) {
730                     if (&e->list_node != list_front(&slave->entries)) {
731                         ds_put_cstr(&ds, " + ");
732                     }
733                     ds_put_format(&ds, "h%td: %"PRIu64"kB",
734                                   e - bond->hash, e->tx_bytes / 1024);
735                 }
736                 ds_put_cstr(&ds, ")");
737             }
738         }
739         VLOG_DBG("bond %s:%s", bond->name, ds_cstr(&ds));
740         ds_destroy(&ds);
741     }
742 }
743
744 /* Shifts 'hash' from its current slave to 'to'. */
745 static void
746 bond_shift_load(struct bond_entry *hash, struct bond_slave *to,
747                 struct tag_set *set)
748 {
749     struct bond_slave *from = hash->slave;
750     struct bond *bond = from->bond;
751     uint64_t delta = hash->tx_bytes;
752
753     VLOG_INFO("bond %s: shift %"PRIu64"kB of load (with hash %td) "
754               "from %s to %s (now carrying %"PRIu64"kB and "
755               "%"PRIu64"kB load, respectively)",
756               bond->name, delta / 1024, hash - bond->hash,
757               from->name, to->name,
758               (from->tx_bytes - delta) / 1024,
759               (to->tx_bytes + delta) / 1024);
760
761     /* Shift load away from 'from' to 'to'. */
762     from->tx_bytes -= delta;
763     to->tx_bytes += delta;
764
765     /* Arrange for flows to be revalidated. */
766     tag_set_add(set, hash->tag);
767     hash->slave = to;
768     hash->tag = tag_create_random();
769 }
770
771 /* Pick and returns a bond_entry to migrate to 'to' (the least-loaded slave),
772  * given that doing so must decrease the ratio of the load on the two slaves by
773  * at least 0.1.  Returns NULL if there is no appropriate entry.
774  *
775  * The list of entries isn't sorted.  I don't know of a reason to prefer to
776  * shift away small hashes or large hashes. */
777 static struct bond_entry *
778 choose_entry_to_migrate(const struct bond_slave *from, uint64_t to_tx_bytes)
779 {
780     struct bond_entry *e;
781
782     if (list_is_short(&from->entries)) {
783         /* 'from' carries no more than one MAC hash, so shifting load away from
784          * it would be pointless. */
785         return NULL;
786     }
787
788     LIST_FOR_EACH (e, list_node, &from->entries) {
789         double old_ratio, new_ratio;
790         uint64_t delta;
791
792         if (to_tx_bytes == 0) {
793             /* Nothing on the new slave, move it. */
794             return e;
795         }
796
797         delta = e->tx_bytes;
798         old_ratio = (double)from->tx_bytes / to_tx_bytes;
799         new_ratio = (double)(from->tx_bytes - delta) / (to_tx_bytes + delta);
800         if (old_ratio - new_ratio > 0.1) {
801             /* Would decrease the ratio, move it. */
802             return e;
803         }
804     }
805
806     return NULL;
807 }
808
809 /* Inserts 'slave' into 'bals' so that descending order of 'tx_bytes' is
810  * maintained. */
811 static void
812 insert_bal(struct list *bals, struct bond_slave *slave)
813 {
814     struct bond_slave *pos;
815
816     LIST_FOR_EACH (pos, bal_node, bals) {
817         if (slave->tx_bytes > pos->tx_bytes) {
818             break;
819         }
820     }
821     list_insert(&pos->bal_node, &slave->bal_node);
822 }
823
824 /* Removes 'slave' from its current list and then inserts it into 'bals' so
825  * that descending order of 'tx_bytes' is maintained. */
826 static void
827 reinsert_bal(struct list *bals, struct bond_slave *slave)
828 {
829     list_remove(&slave->bal_node);
830     insert_bal(bals, slave);
831 }
832
833 /* If 'bond' needs rebalancing, does so.
834  *
835  * The caller should have called bond_account() for each active flow, to ensure
836  * that flow data is consistently accounted at this point. */
837 void
838 bond_rebalance(struct bond *bond, struct tag_set *tags)
839 {
840     struct bond_slave *slave;
841     struct bond_entry *e;
842     struct list bals;
843
844     if (!bond_is_balanced(bond) || time_msec() < bond->next_rebalance) {
845         return;
846     }
847     bond->next_rebalance = time_msec() + bond->rebalance_interval;
848
849     /* Add each bond_entry to its slave's 'entries' list.
850      * Compute each slave's tx_bytes as the sum of its entries' tx_bytes. */
851     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
852         slave->tx_bytes = 0;
853         list_init(&slave->entries);
854     }
855     for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
856         if (e->slave && e->tx_bytes) {
857             e->slave->tx_bytes += e->tx_bytes;
858             list_push_back(&e->slave->entries, &e->list_node);
859         }
860     }
861
862     /* Add enabled slaves to 'bals' in descending order of tx_bytes.
863      *
864      * XXX This is O(n**2) in the number of slaves but it could be O(n lg n)
865      * with a proper list sort algorithm. */
866     list_init(&bals);
867     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
868         if (slave->enabled) {
869             insert_bal(&bals, slave);
870         }
871     }
872     log_bals(bond, &bals);
873
874     /* Shift load from the most-loaded slaves to the least-loaded slaves. */
875     while (!list_is_short(&bals)) {
876         struct bond_slave *from = bond_slave_from_bal_node(list_front(&bals));
877         struct bond_slave *to = bond_slave_from_bal_node(list_back(&bals));
878         uint64_t overload;
879
880         overload = from->tx_bytes - to->tx_bytes;
881         if (overload < to->tx_bytes >> 5 || overload < 100000) {
882             /* The extra load on 'from' (and all less-loaded slaves), compared
883              * to that of 'to' (the least-loaded slave), is less than ~3%, or
884              * it is less than ~1Mbps.  No point in rebalancing. */
885             break;
886         }
887
888         /* 'from' is carrying significantly more load than 'to', and that load
889          * is split across at least two different hashes. */
890         e = choose_entry_to_migrate(from, to->tx_bytes);
891         if (e) {
892             bond_shift_load(e, to, tags);
893
894             /* Delete element from from->entries.
895              *
896              * We don't add the element to to->hashes.  That would only allow
897              * 'e' to be migrated to another slave in this rebalancing run, and
898              * there is no point in doing that. */
899             list_remove(&e->list_node);
900
901             /* Re-sort 'bals'. */
902             reinsert_bal(&bals, from);
903             reinsert_bal(&bals, to);
904         } else {
905             /* Can't usefully migrate anything away from 'from'.
906              * Don't reconsider it. */
907             list_remove(&from->bal_node);
908         }
909     }
910
911     /* Implement exponentially weighted moving average.  A weight of 1/2 causes
912      * historical data to decay to <1% in 7 rebalancing runs.  1,000,000 bytes
913      * take 20 rebalancing runs to decay to 0 and get deleted entirely. */
914     for (e = &bond->hash[0]; e <= &bond->hash[BOND_MASK]; e++) {
915         e->tx_bytes /= 2;
916         if (!e->tx_bytes) {
917             e->slave = NULL;
918         }
919     }
920 }
921 \f
922 /* Bonding unixctl user interface functions. */
923
924 static struct bond *
925 bond_find(const char *name)
926 {
927     struct bond *bond;
928
929     HMAP_FOR_EACH_WITH_HASH (bond, hmap_node, hash_string(name, 0),
930                              &all_bonds) {
931         if (!strcmp(bond->name, name)) {
932             return bond;
933         }
934     }
935     return NULL;
936 }
937
938 static struct bond_slave *
939 bond_lookup_slave(struct bond *bond, const char *slave_name)
940 {
941     struct bond_slave *slave;
942
943     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
944         if (!strcmp(slave->name, slave_name)) {
945             return slave;
946         }
947     }
948     return NULL;
949 }
950
951 static void
952 bond_unixctl_list(struct unixctl_conn *conn,
953                   const char *args OVS_UNUSED, void *aux OVS_UNUSED)
954 {
955     struct ds ds = DS_EMPTY_INITIALIZER;
956     const struct bond *bond;
957
958     ds_put_cstr(&ds, "bond\ttype\tslaves\n");
959
960     HMAP_FOR_EACH (bond, hmap_node, &all_bonds) {
961         const struct bond_slave *slave;
962         size_t i;
963
964         ds_put_format(&ds, "%s\t%s\t",
965                       bond->name, bond_mode_to_string(bond->balance));
966
967         i = 0;
968         HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
969             if (i++ > 0) {
970                 ds_put_cstr(&ds, ", ");
971             }
972             ds_put_cstr(&ds, slave->name);
973         }
974         ds_put_char(&ds, '\n');
975     }
976     unixctl_command_reply(conn, 200, ds_cstr(&ds));
977     ds_destroy(&ds);
978 }
979
980 static void
981 bond_unixctl_show(struct unixctl_conn *conn,
982                   const char *args, void *aux OVS_UNUSED)
983 {
984     struct ds ds = DS_EMPTY_INITIALIZER;
985     const struct bond_slave *slave;
986     const struct bond *bond;
987
988     bond = bond_find(args);
989     if (!bond) {
990         unixctl_command_reply(conn, 501, "no such bond");
991         return;
992     }
993
994     ds_put_format(&ds, "bond_mode: %s\n",
995                   bond_mode_to_string(bond->balance));
996
997     if (bond->lacp) {
998         ds_put_format(&ds, "lacp: %s\n",
999                       lacp_is_active(bond->lacp) ? "active" : "passive");
1000     } else {
1001         ds_put_cstr(&ds, "lacp: off\n");
1002     }
1003
1004     if (bond->balance != BM_AB) {
1005         ds_put_format(&ds, "bond-hash-algorithm: %s\n",
1006                       bond_is_tcp_hash(bond) ? "balance-tcp" : "balance-slb");
1007     }
1008
1009     ds_put_format(&ds, "bond-detect-mode: %s\n",
1010                   bond->monitor ? "carrier" : "miimon");
1011
1012     if (!bond->monitor) {
1013         ds_put_format(&ds, "bond-miimon-interval: %lld\n",
1014                       bond->miimon_interval);
1015     }
1016
1017     ds_put_format(&ds, "updelay: %d ms\n", bond->updelay);
1018     ds_put_format(&ds, "downdelay: %d ms\n", bond->downdelay);
1019
1020     if (bond_is_balanced(bond)) {
1021         ds_put_format(&ds, "next rebalance: %lld ms\n",
1022                       bond->next_rebalance - time_msec());
1023     }
1024
1025     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1026         struct bond_entry *be;
1027         struct flow flow;
1028
1029         /* Basic info. */
1030         ds_put_format(&ds, "\nslave %s: %s\n",
1031                       slave->name, slave->enabled ? "enabled" : "disabled");
1032         if (slave == bond->active_slave) {
1033             ds_put_cstr(&ds, "\tactive slave\n");
1034         }
1035         if (slave->delay_expires != LLONG_MAX) {
1036             ds_put_format(&ds, "\t%s expires in %lld ms\n",
1037                           slave->enabled ? "downdelay" : "updelay",
1038                           slave->delay_expires - time_msec());
1039         }
1040
1041         if (!bond_is_balanced(bond)) {
1042             continue;
1043         }
1044
1045         /* Hashes. */
1046         memset(&flow, 0, sizeof flow);
1047         for (be = bond->hash; be <= &bond->hash[BOND_MASK]; be++) {
1048             int hash = be - bond->hash;
1049
1050             if (be->slave != slave) {
1051                 continue;
1052             }
1053
1054             ds_put_format(&ds, "\thash %d: %"PRIu64" kB load\n",
1055                           hash, be->tx_bytes / 1024);
1056
1057             if (bond->balance != BM_SLB) {
1058                 continue;
1059             }
1060
1061             /* XXX How can we list the MACs assigned to hashes? */
1062         }
1063     }
1064     unixctl_command_reply(conn, 200, ds_cstr(&ds));
1065     ds_destroy(&ds);
1066 }
1067
1068 static void
1069 bond_unixctl_migrate(struct unixctl_conn *conn, const char *args_,
1070                      void *aux OVS_UNUSED)
1071 {
1072     char *args = (char *) args_;
1073     char *save_ptr = NULL;
1074     char *bond_s, *hash_s, *slave_s;
1075     struct bond *bond;
1076     struct bond_slave *slave;
1077     struct bond_entry *entry;
1078     int hash;
1079
1080     bond_s = strtok_r(args, " ", &save_ptr);
1081     hash_s = strtok_r(NULL, " ", &save_ptr);
1082     slave_s = strtok_r(NULL, " ", &save_ptr);
1083     if (!slave_s) {
1084         unixctl_command_reply(conn, 501,
1085                               "usage: bond/migrate BOND HASH SLAVE");
1086         return;
1087     }
1088
1089     bond = bond_find(bond_s);
1090     if (!bond) {
1091         unixctl_command_reply(conn, 501, "no such bond");
1092         return;
1093     }
1094
1095     if (bond->balance != BM_SLB) {
1096         unixctl_command_reply(conn, 501, "not an SLB bond");
1097         return;
1098     }
1099
1100     if (strspn(hash_s, "0123456789") == strlen(hash_s)) {
1101         hash = atoi(hash_s) & BOND_MASK;
1102     } else {
1103         unixctl_command_reply(conn, 501, "bad hash");
1104         return;
1105     }
1106
1107     slave = bond_lookup_slave(bond, slave_s);
1108     if (!slave) {
1109         unixctl_command_reply(conn, 501, "no such slave");
1110         return;
1111     }
1112
1113     if (!slave->enabled) {
1114         unixctl_command_reply(conn, 501, "cannot migrate to disabled slave");
1115         return;
1116     }
1117
1118     entry = &bond->hash[hash];
1119     tag_set_add(&bond->unixctl_tags, entry->tag);
1120     entry->slave = slave;
1121     entry->tag = tag_create_random();
1122     unixctl_command_reply(conn, 200, "migrated");
1123 }
1124
1125 static void
1126 bond_unixctl_set_active_slave(struct unixctl_conn *conn, const char *args_,
1127                               void *aux OVS_UNUSED)
1128 {
1129     char *args = (char *) args_;
1130     char *save_ptr = NULL;
1131     char *bond_s, *slave_s;
1132     struct bond *bond;
1133     struct bond_slave *slave;
1134
1135     bond_s = strtok_r(args, " ", &save_ptr);
1136     slave_s = strtok_r(NULL, " ", &save_ptr);
1137     if (!slave_s) {
1138         unixctl_command_reply(conn, 501,
1139                               "usage: bond/set-active-slave BOND SLAVE");
1140         return;
1141     }
1142
1143     bond = bond_find(bond_s);
1144     if (!bond) {
1145         unixctl_command_reply(conn, 501, "no such bond");
1146         return;
1147     }
1148
1149     slave = bond_lookup_slave(bond, slave_s);
1150     if (!slave) {
1151         unixctl_command_reply(conn, 501, "no such slave");
1152         return;
1153     }
1154
1155     if (!slave->enabled) {
1156         unixctl_command_reply(conn, 501, "cannot make disabled slave active");
1157         return;
1158     }
1159
1160     if (bond->active_slave != slave) {
1161         tag_set_add(&bond->unixctl_tags, bond_get_active_slave_tag(bond));
1162         bond->active_slave = slave;
1163         bond->active_slave->tag = tag_create_random();
1164         VLOG_INFO("bond %s: active interface is now %s",
1165                   bond->name, slave->name);
1166         bond->send_learning_packets = true;
1167         unixctl_command_reply(conn, 200, "done");
1168     } else {
1169         unixctl_command_reply(conn, 200, "no change");
1170     }
1171 }
1172
1173 static void
1174 enable_slave(struct unixctl_conn *conn, const char *args_, bool enable)
1175 {
1176     char *args = (char *) args_;
1177     char *save_ptr = NULL;
1178     char *bond_s, *slave_s;
1179     struct bond *bond;
1180     struct bond_slave *slave;
1181
1182     bond_s = strtok_r(args, " ", &save_ptr);
1183     slave_s = strtok_r(NULL, " ", &save_ptr);
1184     if (!slave_s) {
1185         char *usage = xasprintf("usage: bond/%s-slave BOND SLAVE",
1186                                 enable ? "enable" : "disable");
1187         unixctl_command_reply(conn, 501, usage);
1188         free(usage);
1189         return;
1190     }
1191
1192     bond = bond_find(bond_s);
1193     if (!bond) {
1194         unixctl_command_reply(conn, 501, "no such bond");
1195         return;
1196     }
1197
1198     slave = bond_lookup_slave(bond, slave_s);
1199     if (!slave) {
1200         unixctl_command_reply(conn, 501, "no such slave");
1201         return;
1202     }
1203
1204     bond_enable_slave(slave, enable, &bond->unixctl_tags);
1205     unixctl_command_reply(conn, 501, enable ? "enabled" : "disabled");
1206 }
1207
1208 static void
1209 bond_unixctl_enable_slave(struct unixctl_conn *conn, const char *args,
1210                           void *aux OVS_UNUSED)
1211 {
1212     enable_slave(conn, args, true);
1213 }
1214
1215 static void
1216 bond_unixctl_disable_slave(struct unixctl_conn *conn, const char *args,
1217                            void *aux OVS_UNUSED)
1218 {
1219     enable_slave(conn, args, false);
1220 }
1221
1222 static void
1223 bond_unixctl_hash(struct unixctl_conn *conn, const char *args_,
1224                   void *aux OVS_UNUSED)
1225 {
1226     char *args = (char *) args_;
1227     uint8_t mac[ETH_ADDR_LEN];
1228     uint8_t hash;
1229     char *hash_cstr;
1230     unsigned int vlan;
1231     char *mac_s, *vlan_s;
1232     char *save_ptr = NULL;
1233
1234     mac_s  = strtok_r(args, " ", &save_ptr);
1235     vlan_s = strtok_r(NULL, " ", &save_ptr);
1236
1237     if (vlan_s) {
1238         if (sscanf(vlan_s, "%u", &vlan) != 1) {
1239             unixctl_command_reply(conn, 501, "invalid vlan");
1240             return;
1241         }
1242     } else {
1243         vlan = OFP_VLAN_NONE;
1244     }
1245
1246     if (sscanf(mac_s, ETH_ADDR_SCAN_FMT, ETH_ADDR_SCAN_ARGS(mac))
1247         == ETH_ADDR_SCAN_COUNT) {
1248         hash = bond_hash_src(mac, vlan) & BOND_MASK;
1249
1250         hash_cstr = xasprintf("%u", hash);
1251         unixctl_command_reply(conn, 200, hash_cstr);
1252         free(hash_cstr);
1253     } else {
1254         unixctl_command_reply(conn, 501, "invalid mac");
1255     }
1256 }
1257
1258 void
1259 bond_init(void)
1260 {
1261     lacp_init();
1262
1263     unixctl_command_register("bond/list", bond_unixctl_list, NULL);
1264     unixctl_command_register("bond/show", bond_unixctl_show, NULL);
1265     unixctl_command_register("bond/migrate", bond_unixctl_migrate, NULL);
1266     unixctl_command_register("bond/set-active-slave",
1267                              bond_unixctl_set_active_slave, NULL);
1268     unixctl_command_register("bond/enable-slave", bond_unixctl_enable_slave,
1269                              NULL);
1270     unixctl_command_register("bond/disable-slave", bond_unixctl_disable_slave,
1271                              NULL);
1272     unixctl_command_register("bond/hash", bond_unixctl_hash, NULL);
1273 }
1274 \f
1275 static void
1276 bond_entry_reset(struct bond *bond)
1277 {
1278     if (bond->balance != BM_AB) {
1279         size_t hash_len = (BOND_MASK + 1) * sizeof *bond->hash;
1280
1281         if (!bond->hash) {
1282             bond->hash = xmalloc(hash_len);
1283         }
1284         memset(bond->hash, 0, hash_len);
1285
1286         bond->next_rebalance = time_msec() + bond->rebalance_interval;
1287     } else {
1288         free(bond->hash);
1289         bond->hash = NULL;
1290     }
1291 }
1292
1293 static struct bond_slave *
1294 bond_slave_lookup(struct bond *bond, const void *slave_)
1295 {
1296     struct bond_slave *slave;
1297
1298     HMAP_FOR_EACH_IN_BUCKET (slave, hmap_node, hash_pointer(slave_, 0),
1299                              &bond->slaves) {
1300         if (slave->aux == slave_) {
1301             return slave;
1302         }
1303     }
1304
1305     return NULL;
1306 }
1307
1308 static bool
1309 bond_is_link_up(struct bond *bond, struct netdev *netdev)
1310 {
1311     return (bond->detect == BLSM_CARRIER
1312             ? netdev_get_carrier(netdev)
1313             : netdev_get_miimon(netdev));
1314 }
1315
1316 static void
1317 bond_enable_slave(struct bond_slave *slave, bool enable, struct tag_set *tags)
1318 {
1319     slave->delay_expires = LLONG_MAX;
1320     if (enable != slave->enabled) {
1321         slave->enabled = enable;
1322         if (!slave->enabled) {
1323             VLOG_WARN("interface %s: disabled", slave->name);
1324             if (tags) {
1325                 tag_set_add(tags, slave->tag);
1326             }
1327         } else {
1328             VLOG_WARN("interface %s: enabled", slave->name);
1329             slave->tag = tag_create_random();
1330         }
1331     }
1332 }
1333
1334 static void
1335 bond_link_status_update(struct bond_slave *slave, struct tag_set *tags)
1336 {
1337     struct bond *bond = slave->bond;
1338     bool up;
1339
1340     up = slave->up && lacp_slave_may_enable(bond->lacp, slave);
1341     if ((up == slave->enabled) != (slave->delay_expires == LLONG_MAX)) {
1342         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1343         VLOG_INFO_RL(&rl, "interface %s: link state %s",
1344                      slave->name, up ? "up" : "down");
1345         if (up == slave->enabled) {
1346             slave->delay_expires = LLONG_MAX;
1347             VLOG_INFO_RL(&rl, "interface %s: will not be %s",
1348                          slave->name, up ? "disabled" : "enabled");
1349         } else {
1350             int delay = (lacp_negotiated(bond->lacp) ? 0
1351                          : up ? bond->updelay : bond->downdelay);
1352             slave->delay_expires = time_msec() + delay;
1353             if (delay) {
1354                 VLOG_INFO_RL(&rl, "interface %s: will be %s if it stays %s "
1355                              "for %d ms",
1356                              slave->name,
1357                              up ? "enabled" : "disabled",
1358                              up ? "up" : "down",
1359                              delay);
1360             }
1361         }
1362     }
1363
1364     if (time_msec() >= slave->delay_expires) {
1365         bond_enable_slave(slave, up, tags);
1366     }
1367 }
1368
1369 static bool
1370 bond_is_tcp_hash(const struct bond *bond)
1371 {
1372     return bond->balance == BM_TCP && lacp_negotiated(bond->lacp);
1373 }
1374
1375 static unsigned int
1376 bond_hash_src(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
1377 {
1378     return hash_bytes(mac, ETH_ADDR_LEN, vlan);
1379 }
1380
1381 static unsigned int
1382 bond_hash_tcp(const struct flow *flow, uint16_t vlan)
1383 {
1384     struct flow hash_flow = *flow;
1385     hash_flow.vlan_tci = vlan;
1386
1387     /* The symmetric quality of this hash function is not required, but
1388      * flow_hash_symmetric_l4 already exists, and is sufficient for our
1389      * purposes, so we use it out of convenience. */
1390     return flow_hash_symmetric_l4(&hash_flow, 0);
1391 }
1392
1393 static struct bond_entry *
1394 lookup_bond_entry(const struct bond *bond, const struct flow *flow,
1395                   uint16_t vlan)
1396 {
1397     assert(bond->balance != BM_AB);
1398     return &bond->hash[(bond_is_tcp_hash(bond)
1399                         ? bond_hash_tcp(flow, vlan)
1400                         : bond_hash_src(flow->dl_src, vlan)) & BOND_MASK];
1401 }
1402
1403 static struct bond_slave *
1404 choose_output_slave(const struct bond *bond, const struct flow *flow,
1405                     uint16_t vlan)
1406 {
1407     struct bond_entry *e;
1408
1409     switch (bond->balance) {
1410     case BM_AB:
1411         return bond->active_slave;
1412
1413     case BM_SLB:
1414     case BM_TCP:
1415         e = lookup_bond_entry(bond, flow, vlan);
1416         if (!e->slave || !e->slave->enabled) {
1417             e->slave = CONTAINER_OF(hmap_random_node(&bond->slaves),
1418                                     struct bond_slave, hmap_node);
1419             if (!e->slave->enabled) {
1420                 e->slave = bond->active_slave;
1421             }
1422             e->tag = tag_create_random();
1423         }
1424         return e->slave;
1425
1426     default:
1427         NOT_REACHED();
1428     }
1429 }
1430
1431 static struct bond_slave *
1432 bond_choose_slave(const struct bond *bond)
1433 {
1434     struct bond_slave *slave, *best;
1435
1436     /* Find an enabled slave. */
1437     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1438         if (slave->enabled) {
1439             return slave;
1440         }
1441     }
1442
1443     /* All interfaces are disabled.  Find an interface that will be enabled
1444      * after its updelay expires.  */
1445     best = NULL;
1446     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1447         if (slave->delay_expires != LLONG_MAX
1448             && lacp_slave_may_enable(bond->lacp, slave)
1449             && (!best || slave->delay_expires < best->delay_expires)) {
1450             best = slave;
1451         }
1452     }
1453     return best;
1454 }
1455
1456 static void
1457 bond_choose_active_slave(struct bond *bond, struct tag_set *tags)
1458 {
1459     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
1460     struct bond_slave *old_active_slave = bond->active_slave;
1461
1462     bond->active_slave = bond_choose_slave(bond);
1463     if (bond->active_slave) {
1464         if (bond->active_slave->enabled) {
1465             VLOG_INFO_RL(&rl, "bond %s: active interface is now %s",
1466                          bond->name, bond->active_slave->name);
1467         } else {
1468             VLOG_INFO_RL(&rl, "bond %s: active interface is now %s, skipping "
1469                          "remaining %lld ms updelay (since no interface was "
1470                          "enabled)", bond->name, bond->active_slave->name,
1471                          bond->active_slave->delay_expires - time_msec());
1472             bond_enable_slave(bond->active_slave, true, tags);
1473         }
1474
1475         if (!old_active_slave) {
1476             tag_set_add(tags, bond->no_slaves_tag);
1477         }
1478
1479         bond->send_learning_packets = true;
1480     } else if (old_active_slave) {
1481         VLOG_WARN_RL(&rl, "bond %s: all interfaces disabled", bond->name);
1482     }
1483 }
1484
1485 /* Returns the tag for 'bond''s active slave, or 'bond''s no_slaves_tag if
1486  * there is no active slave. */
1487 static tag_type
1488 bond_get_active_slave_tag(const struct bond *bond)
1489 {
1490     return (bond->active_slave
1491             ? bond->active_slave->tag
1492             : bond->no_slaves_tag);
1493 }
1494
1495 /* Attempts to make the sum of the bond slaves' statistics appear on the fake
1496  * bond interface. */
1497 static void
1498 bond_update_fake_slave_stats(struct bond *bond)
1499 {
1500     struct netdev_stats bond_stats;
1501     struct bond_slave *slave;
1502     struct netdev *bond_dev;
1503
1504     memset(&bond_stats, 0, sizeof bond_stats);
1505
1506     HMAP_FOR_EACH (slave, hmap_node, &bond->slaves) {
1507         struct netdev_stats slave_stats;
1508
1509         if (!netdev_get_stats(slave->netdev, &slave_stats)) {
1510             /* XXX: We swap the stats here because they are swapped back when
1511              * reported by the internal device.  The reason for this is
1512              * internal devices normally represent packets going into the
1513              * system but when used as fake bond device they represent packets
1514              * leaving the system.  We really should do this in the internal
1515              * device itself because changing it here reverses the counts from
1516              * the perspective of the switch.  However, the internal device
1517              * doesn't know what type of device it represents so we have to do
1518              * it here for now. */
1519             bond_stats.tx_packets += slave_stats.rx_packets;
1520             bond_stats.tx_bytes += slave_stats.rx_bytes;
1521             bond_stats.rx_packets += slave_stats.tx_packets;
1522             bond_stats.rx_bytes += slave_stats.tx_bytes;
1523         }
1524     }
1525
1526     if (!netdev_open_default(bond->name, &bond_dev)) {
1527         netdev_set_stats(bond_dev, &bond_stats);
1528         netdev_close(bond_dev);
1529     }
1530 }