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