New action NXAST_RESUBMIT_TABLE.
[openvswitch] / lib / cfm.c
1 /*
2  * Copyright (c) 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 #include "cfm.h"
19
20 #include <assert.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #include "dynamic-string.h"
26 #include "flow.h"
27 #include "hash.h"
28 #include "hmap.h"
29 #include "ofpbuf.h"
30 #include "packets.h"
31 #include "poll-loop.h"
32 #include "timer.h"
33 #include "timeval.h"
34 #include "unixctl.h"
35 #include "vlog.h"
36
37 VLOG_DEFINE_THIS_MODULE(cfm);
38
39 /* Ethernet destination address of CCM packets. */
40 static const uint8_t eth_addr_ccm[6] = { 0x01, 0x80, 0xC2, 0x00, 0x00, 0x30 };
41
42 #define ETH_TYPE_CFM 0x8902
43
44 /* A 'ccm' represents a Continuity Check Message from the 802.1ag
45  * specification.  Continuity Check Messages are broadcast periodically so that
46  * hosts can determine whom they have connectivity to. */
47 #define CCM_LEN 74
48 #define CCM_MAID_LEN 48
49 #define CCM_OPCODE 1 /* CFM message opcode meaning CCM. */
50 #define CCM_RDI_MASK 0x80
51 struct ccm {
52     uint8_t  mdlevel_version; /* MD Level and Version */
53     uint8_t  opcode;
54     uint8_t  flags;
55     uint8_t  tlv_offset;
56     ovs_be32 seq;
57     ovs_be16 mpid;
58     uint8_t  maid[CCM_MAID_LEN];
59     uint8_t  zero[16]; /* Defined by ITU-T Y.1731 should be zero */
60 } __attribute__((packed));
61 BUILD_ASSERT_DECL(CCM_LEN == sizeof(struct ccm));
62
63 struct cfm {
64     char *name;                 /* Name of this CFM object. */
65     struct hmap_node hmap_node; /* Node in all_cfms list. */
66
67     uint16_t mpid;
68     bool fault;            /* Indicates connectivity fault. */
69     bool recv_fault;       /* Indicates an inability to receive CCMs. */
70
71     uint32_t seq;          /* The sequence number of our last CCM. */
72     uint8_t ccm_interval;  /* The CCM transmission interval. */
73     int ccm_interval_ms;   /* 'ccm_interval' in milliseconds. */
74     uint8_t maid[CCM_MAID_LEN]; /* The MAID of this CFM. */
75
76     struct timer tx_timer;    /* Send CCM when expired. */
77     struct timer fault_timer; /* Check for faults when expired. */
78
79     struct hmap remote_mps; /* Expected remote MPs. */
80 };
81
82 /* Remote MPs represent foreign network entities that are configured to have
83  * the same MAID as this CFM instance. */
84 struct remote_mp {
85     uint16_t mpid;         /* The Maintenance Point ID of this 'remote_mp'. */
86     struct hmap_node node; /* Node in 'remote_mps' map. */
87
88     bool recv;           /* CCM was received since last fault check. */
89     bool fault;          /* Indicates a connectivity fault. */
90     bool rdi;            /* Remote Defect Indicator. Indicates remote_mp isn't
91                             receiving CCMs that it's expecting to. */
92 };
93
94 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 20);
95 static struct hmap all_cfms = HMAP_INITIALIZER(&all_cfms);
96
97 static void cfm_unixctl_show(struct unixctl_conn *, const char *args,
98                              void *aux);
99
100 static void
101 cfm_generate_maid(struct cfm *cfm)
102 {
103     const char *ovs_md_name = "ovs";
104     const char *ovs_ma_name = "ovs";
105     uint8_t *ma_p;
106     size_t md_len, ma_len;
107
108     memset(cfm->maid, 0, CCM_MAID_LEN);
109
110     md_len = strlen(ovs_md_name);
111     ma_len = strlen(ovs_ma_name);
112
113     assert(md_len && ma_len && md_len + ma_len + 4 <= CCM_MAID_LEN);
114
115     cfm->maid[0] = 4;                           /* MD name string format. */
116     cfm->maid[1] = md_len;                      /* MD name size. */
117     memcpy(&cfm->maid[2], ovs_md_name, md_len); /* MD name. */
118
119     ma_p = cfm->maid + 2 + md_len;
120     ma_p[0] = 2;                           /* MA name string format. */
121     ma_p[1] = ma_len;                      /* MA name size. */
122     memcpy(&ma_p[2], ovs_ma_name, ma_len); /* MA name. */
123 }
124
125 static int
126 ccm_interval_to_ms(uint8_t interval)
127 {
128     switch (interval) {
129     case 0:  NOT_REACHED(); /* Explicitly not supported by 802.1ag. */
130     case 1:  return 3;      /* Not recommended due to timer resolution. */
131     case 2:  return 10;     /* Not recommended due to timer resolution. */
132     case 3:  return 100;
133     case 4:  return 1000;
134     case 5:  return 10000;
135     case 6:  return 60000;
136     case 7:  return 600000;
137     default: NOT_REACHED(); /* Explicitly not supported by 802.1ag. */
138     }
139
140     NOT_REACHED();
141 }
142
143 static long long int
144 cfm_fault_interval(struct cfm *cfm)
145 {
146     /* According to the 802.1ag specification we should assume every other MP
147      * with the same MAID has the same transmission interval that we have.  If
148      * an MP has a different interval, cfm_process_heartbeat will register it
149      * as a fault (likely due to a configuration error).  Thus we can check all
150      * MPs at once making this quite a bit simpler.
151      *
152      * According to the specification we should check when (ccm_interval_ms *
153      * 3.5)ms have passed. */
154     return (cfm->ccm_interval_ms * 7) / 2;
155 }
156
157 static uint8_t
158 ms_to_ccm_interval(int interval_ms)
159 {
160     uint8_t i;
161
162     for (i = 7; i > 0; i--) {
163         if (ccm_interval_to_ms(i) <= interval_ms) {
164             return i;
165         }
166     }
167
168     return 1;
169 }
170
171 static uint32_t
172 hash_mpid(uint8_t mpid)
173 {
174     return hash_int(mpid, 0);
175 }
176
177 static bool
178 cfm_is_valid_mpid(uint32_t mpid)
179 {
180     /* 802.1ag specification requires MPIDs to be within the range [1, 8191] */
181     return mpid >= 1 && mpid <= 8191;
182 }
183
184 static struct remote_mp *
185 lookup_remote_mp(const struct hmap *hmap, uint16_t mpid)
186 {
187     struct remote_mp *rmp;
188
189     HMAP_FOR_EACH_IN_BUCKET (rmp, node, hash_mpid(mpid), hmap) {
190         if (rmp->mpid == mpid) {
191             return rmp;
192         }
193     }
194
195     return NULL;
196 }
197
198 void
199 cfm_init(void)
200 {
201     unixctl_command_register("cfm/show", cfm_unixctl_show, NULL);
202 }
203
204 /* Allocates a 'cfm' object called 'name'.  'cfm' should be initialized by
205  * cfm_configure() before use. */
206 struct cfm *
207 cfm_create(const char *name)
208 {
209     struct cfm *cfm;
210
211     cfm = xzalloc(sizeof *cfm);
212     cfm->name = xstrdup(name);
213     hmap_init(&cfm->remote_mps);
214     cfm_generate_maid(cfm);
215     hmap_insert(&all_cfms, &cfm->hmap_node, hash_string(cfm->name, 0));
216     return cfm;
217 }
218
219 void
220 cfm_destroy(struct cfm *cfm)
221 {
222     struct remote_mp *rmp, *rmp_next;
223
224     if (!cfm) {
225         return;
226     }
227
228     HMAP_FOR_EACH_SAFE (rmp, rmp_next, node, &cfm->remote_mps) {
229         hmap_remove(&cfm->remote_mps, &rmp->node);
230         free(rmp);
231     }
232
233     hmap_destroy(&cfm->remote_mps);
234     hmap_remove(&all_cfms, &cfm->hmap_node);
235     free(cfm->name);
236     free(cfm);
237 }
238
239 /* Should be run periodically to update fault statistics messages. */
240 void
241 cfm_run(struct cfm *cfm)
242 {
243     if (timer_expired(&cfm->fault_timer)) {
244         long long int interval = cfm_fault_interval(cfm);
245         struct remote_mp *rmp;
246
247         cfm->fault = false;
248         cfm->recv_fault = false;
249         HMAP_FOR_EACH (rmp, node, &cfm->remote_mps) {
250             rmp->fault = !rmp->recv;
251             rmp->recv = false;
252
253             if (rmp->fault) {
254                 cfm->recv_fault = true;
255                 VLOG_DBG("%s: No CCM from RMP %"PRIu16" in the last %lldms",
256                          cfm->name, rmp->mpid, interval);
257             } else if (rmp->rdi) {
258                 cfm->fault = true;
259                 VLOG_DBG("%s: RDI bit flagged from RMP %"PRIu16, cfm->name,
260                          rmp->mpid);
261             }
262         }
263
264         if (cfm->recv_fault) {
265             cfm->fault = true;
266         } else {
267             VLOG_DBG("%s: All RMPs received CCMs in the last %lldms",
268                      cfm->name, interval);
269         }
270
271         timer_set_duration(&cfm->fault_timer, interval);
272     }
273 }
274
275 /* Should be run periodically to check if the CFM module has a CCM message it
276  * wishes to send. */
277 bool
278 cfm_should_send_ccm(struct cfm *cfm)
279 {
280     return timer_expired(&cfm->tx_timer);
281 }
282
283 /* Composes a CCM message into 'packet'.  Messages generated with this function
284  * should be sent whenever cfm_should_send_ccm() indicates. */
285 void
286 cfm_compose_ccm(struct cfm *cfm, struct ofpbuf *packet,
287                 uint8_t eth_src[ETH_ADDR_LEN])
288 {
289     struct ccm *ccm;
290
291     timer_set_duration(&cfm->tx_timer, cfm->ccm_interval_ms);
292
293     ccm = eth_compose(packet, eth_addr_ccm, eth_src, ETH_TYPE_CFM,
294                       sizeof *ccm);
295     ccm->mdlevel_version = 0;
296     ccm->opcode = CCM_OPCODE;
297     ccm->tlv_offset = 70;
298     ccm->seq = htonl(++cfm->seq);
299     ccm->mpid = htons(cfm->mpid);
300     ccm->flags = cfm->ccm_interval;
301     memcpy(ccm->maid, cfm->maid, sizeof ccm->maid);
302
303     if (cfm->recv_fault) {
304         ccm->flags |= CCM_RDI_MASK;
305     }
306 }
307
308 void
309 cfm_wait(struct cfm *cfm)
310 {
311
312     timer_wait(&cfm->tx_timer);
313     timer_wait(&cfm->fault_timer);
314 }
315
316 /* Configures 'cfm' with settings from 's'. */
317 bool
318 cfm_configure(struct cfm *cfm, const struct cfm_settings *s)
319 {
320     size_t i;
321     uint8_t interval;
322     struct hmap new_rmps;
323     struct remote_mp *rmp, *rmp_next;
324
325     if (!cfm_is_valid_mpid(s->mpid) || s->interval <= 0
326         || s->n_remote_mpids <= 0) {
327         return false;
328     }
329
330     cfm->mpid = s->mpid;
331     interval = ms_to_ccm_interval(s->interval);
332
333     if (interval != cfm->ccm_interval) {
334         cfm->ccm_interval = interval;
335         cfm->ccm_interval_ms = ccm_interval_to_ms(interval);
336
337         timer_set_expired(&cfm->tx_timer);
338         timer_set_duration(&cfm->fault_timer, cfm_fault_interval(cfm));
339     }
340
341     hmap_init(&new_rmps);
342     for (i = 0; i < s->n_remote_mpids; i++) {
343         uint16_t mpid = s->remote_mpids[i];
344
345         if (!cfm_is_valid_mpid(mpid)
346             || lookup_remote_mp(&new_rmps, mpid)) {
347             continue;
348         }
349
350         if ((rmp = lookup_remote_mp(&cfm->remote_mps, mpid))) {
351             hmap_remove(&cfm->remote_mps, &rmp->node);
352         } else {
353             rmp = xzalloc(sizeof *rmp);
354             rmp->mpid = mpid;
355         }
356
357         hmap_insert(&new_rmps, &rmp->node, hash_mpid(mpid));
358     }
359
360     hmap_swap(&new_rmps, &cfm->remote_mps);
361     HMAP_FOR_EACH_SAFE (rmp, rmp_next, node, &new_rmps) {
362         hmap_remove(&new_rmps, &rmp->node);
363         free(rmp);
364     }
365     hmap_destroy(&new_rmps);
366
367     return true;
368 }
369
370 /* Returns true if the CFM library should process packets from 'flow'. */
371 bool
372 cfm_should_process_flow(const struct flow *flow)
373 {
374     return (ntohs(flow->dl_type) == ETH_TYPE_CFM
375             && eth_addr_equals(flow->dl_dst, eth_addr_ccm));
376 }
377
378 /* Updates internal statistics relevant to packet 'p'.  Should be called on
379  * every packet whose flow returned true when passed to
380  * cfm_should_process_flow. */
381 void
382 cfm_process_heartbeat(struct cfm *cfm, const struct ofpbuf *p)
383 {
384     struct ccm *ccm;
385     bool ccm_rdi;
386     uint16_t ccm_mpid;
387     uint8_t ccm_interval;
388     struct remote_mp *rmp;
389     struct eth_header *eth;
390
391     eth = p->l2;
392     ccm = ofpbuf_at(p, (uint8_t *)p->l3 - (uint8_t *)p->data, CCM_LEN);
393
394     if (!ccm) {
395         VLOG_INFO_RL(&rl, "%s: Received an unparseable 802.1ag CCM heartbeat.",
396                      cfm->name);
397         return;
398     }
399
400     if (ccm->opcode != CCM_OPCODE) {
401         VLOG_INFO_RL(&rl, "%s: Received an unsupported 802.1ag message. "
402                      "(opcode %u)", cfm->name, ccm->opcode);
403         return;
404     }
405
406     /* According to the 802.1ag specification, reception of a CCM with an
407      * incorrect ccm_interval, unexpected MAID, or unexpected MPID should
408      * trigger a fault.  We ignore this requirement for several reasons.
409      *
410      * Faults can cause a controller or Open vSwitch to make potentially
411      * expensive changes to the network topology.  It seems prudent to trigger
412      * them judiciously, especially when CFM is used to check slave status of
413      * bonds. Furthermore, faults can be maliciously triggered by crafting
414      * invalid CCMs. */
415     if (memcmp(ccm->maid, cfm->maid, sizeof ccm->maid)) {
416         VLOG_WARN_RL(&rl, "%s: Received unexpected remote MAID from MAC "
417                      ETH_ADDR_FMT, cfm->name, ETH_ADDR_ARGS(eth->eth_src));
418     } else {
419         ccm_mpid = ntohs(ccm->mpid);
420         ccm_interval = ccm->flags & 0x7;
421         ccm_rdi = ccm->flags & CCM_RDI_MASK;
422
423         rmp = lookup_remote_mp(&cfm->remote_mps, ccm_mpid);
424
425         if (rmp) {
426             rmp->recv = true;
427             rmp->rdi = ccm_rdi;
428
429             if (ccm_interval != cfm->ccm_interval) {
430                 VLOG_WARN_RL(&rl, "%s: received a CCM with an invalid interval"
431                              " (%"PRIu8") from RMP %"PRIu16, cfm->name,
432                              ccm_interval, rmp->mpid);
433             }
434         } else {
435             VLOG_WARN_RL(&rl, "%s: Received unexpected remote MPID %d from"
436                          " MAC " ETH_ADDR_FMT, cfm->name, ccm_mpid,
437                          ETH_ADDR_ARGS(eth->eth_src));
438         }
439
440         VLOG_DBG("%s: Received CCM (seq %"PRIu32") (mpid %"PRIu16")"
441                  " (interval %"PRIu8") (RDI %s)", cfm->name, ntohl(ccm->seq),
442                  ccm_mpid, ccm_interval, ccm_rdi ? "true" : "false");
443     }
444 }
445
446 /* Gets the fault status of 'cfm'.  Returns true when 'cfm' has detected
447  * connectivity problems, false otherwise. */
448 bool
449 cfm_get_fault(const struct cfm *cfm)
450 {
451     return cfm->fault;
452 }
453
454 static struct cfm *
455 cfm_find(const char *name)
456 {
457     struct cfm *cfm;
458
459     HMAP_FOR_EACH_WITH_HASH (cfm, hmap_node, hash_string(name, 0), &all_cfms) {
460         if (!strcmp(cfm->name, name)) {
461             return cfm;
462         }
463     }
464     return NULL;
465 }
466
467 static void
468 cfm_unixctl_show(struct unixctl_conn *conn,
469                  const char *args, void *aux OVS_UNUSED)
470 {
471     struct ds ds = DS_EMPTY_INITIALIZER;
472     const struct cfm *cfm;
473     struct remote_mp *rmp;
474
475     cfm = cfm_find(args);
476     if (!cfm) {
477         unixctl_command_reply(conn, 501, "no such CFM object");
478         return;
479     }
480
481     ds_put_format(&ds, "MPID %"PRIu16":%s%s\n", cfm->mpid,
482                   cfm->fault ? " fault" : "",
483                   cfm->recv_fault ? " recv_fault" : "");
484
485     ds_put_format(&ds, "\tinterval: %dms\n", cfm->ccm_interval_ms);
486     ds_put_format(&ds, "\tnext CCM tx: %lldms\n",
487                   timer_msecs_until_expired(&cfm->tx_timer));
488     ds_put_format(&ds, "\tnext fault check: %lldms\n",
489                   timer_msecs_until_expired(&cfm->fault_timer));
490
491     ds_put_cstr(&ds, "\n");
492     HMAP_FOR_EACH (rmp, node, &cfm->remote_mps) {
493         ds_put_format(&ds, "Remote MPID %"PRIu16": %s\n", rmp->mpid,
494                       rmp->fault ? "fault" : "");
495         ds_put_format(&ds, "\trecv since check: %s",
496                       rmp->recv ? "true" : "false");
497     }
498
499     unixctl_command_reply(conn, 200, ds_cstr(&ds));
500     ds_destroy(&ds);
501 }