netdev-linux: Factor out removing policing.
[openvswitch] / lib / learning-switch.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 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 "learning-switch.h"
19
20 #include <errno.h>
21 #include <inttypes.h>
22 #include <netinet/in.h>
23 #include <stdlib.h>
24 #include <time.h>
25
26 #include "flow.h"
27 #include "mac-learning.h"
28 #include "ofpbuf.h"
29 #include "ofp-print.h"
30 #include "openflow/openflow.h"
31 #include "poll-loop.h"
32 #include "queue.h"
33 #include "rconn.h"
34 #include "stp.h"
35 #include "timeval.h"
36 #include "vconn.h"
37 #include "xtoxll.h"
38
39 #define THIS_MODULE VLM_learning_switch
40 #include "vlog.h"
41
42 enum port_state {
43     P_DISABLED = 1 << 0,
44     P_LISTENING = 1 << 1,
45     P_LEARNING = 1 << 2,
46     P_FORWARDING = 1 << 3,
47     P_BLOCKING = 1 << 4
48 };
49
50 struct lswitch {
51     /* If nonnegative, the switch sets up flows that expire after the given
52      * number of seconds (or never expire, if the value is OFP_FLOW_PERMANENT).
53      * Otherwise, the switch processes every packet. */
54     int max_idle;
55
56     unsigned long long int datapath_id;
57     uint32_t capabilities;
58     time_t last_features_request;
59     struct mac_learning *ml;    /* NULL to act as hub instead of switch. */
60     bool exact_flows;           /* Use exact-match flows? */
61     bool action_normal;         /* Use OFPP_NORMAL? */
62
63     /* Number of outgoing queued packets on the rconn. */
64     struct rconn_packet_counter *queued;
65
66     /* Spanning tree protocol implementation.
67      *
68      * We implement STP states by, whenever a port's STP state changes,
69      * querying all the flows on the switch and then deleting any of them that
70      * are inappropriate for a port's STP state. */
71     long long int next_query;   /* Next time at which to query all flows. */
72     long long int last_query;   /* Last time we sent a query. */
73     long long int last_reply;   /* Last time we received a query reply. */
74     unsigned int port_states[STP_MAX_PORTS];
75     uint32_t query_xid;         /* XID used for query. */
76     int n_flows, n_no_recv, n_no_send;
77 };
78
79 /* The log messages here could actually be useful in debugging, so keep the
80  * rate limit relatively high. */
81 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300);
82
83 static void queue_tx(struct lswitch *, struct rconn *, struct ofpbuf *);
84 static void send_features_request(struct lswitch *, struct rconn *);
85 static void schedule_query(struct lswitch *, long long int delay);
86 static bool may_learn(const struct lswitch *, uint16_t port_no);
87 static bool may_recv(const struct lswitch *, uint16_t port_no,
88                      bool any_actions);
89 static bool may_send(const struct lswitch *, uint16_t port_no);
90
91 typedef void packet_handler_func(struct lswitch *, struct rconn *, void *);
92 static packet_handler_func process_switch_features;
93 static packet_handler_func process_packet_in;
94 static packet_handler_func process_echo_request;
95 static packet_handler_func process_port_status;
96 static packet_handler_func process_phy_port;
97 static packet_handler_func process_stats_reply;
98
99 /* Creates and returns a new learning switch.
100  *
101  * If 'learn_macs' is true, the new switch will learn the ports on which MAC
102  * addresses appear.  Otherwise, the new switch will flood all packets.
103  *
104  * If 'max_idle' is nonnegative, the new switch will set up flows that expire
105  * after the given number of seconds (or never expire, if 'max_idle' is
106  * OFP_FLOW_PERMANENT).  Otherwise, the new switch will process every packet.
107  *
108  * 'rconn' is used to send out an OpenFlow features request. */
109 struct lswitch *
110 lswitch_create(struct rconn *rconn, bool learn_macs,
111                bool exact_flows, int max_idle, bool action_normal)
112 {
113     struct lswitch *sw;
114     size_t i;
115
116     sw = xzalloc(sizeof *sw);
117     sw->max_idle = max_idle;
118     sw->datapath_id = 0;
119     sw->last_features_request = time_now() - 1;
120     sw->ml = learn_macs ? mac_learning_create() : NULL;
121     sw->action_normal = action_normal;
122     sw->exact_flows = exact_flows;
123     sw->queued = rconn_packet_counter_create();
124     sw->next_query = LLONG_MIN;
125     sw->last_query = LLONG_MIN;
126     sw->last_reply = LLONG_MIN;
127     for (i = 0; i < STP_MAX_PORTS; i++) {
128         sw->port_states[i] = P_DISABLED;
129     }
130     send_features_request(sw, rconn);
131     return sw;
132 }
133
134 /* Destroys 'sw'. */
135 void
136 lswitch_destroy(struct lswitch *sw)
137 {
138     if (sw) {
139         mac_learning_destroy(sw->ml);
140         rconn_packet_counter_destroy(sw->queued);
141         free(sw);
142     }
143 }
144
145 /* Takes care of necessary 'sw' activity, except for receiving packets (which
146  * the caller must do). */
147 void
148 lswitch_run(struct lswitch *sw, struct rconn *rconn)
149 {
150     long long int now = time_msec();
151
152     if (sw->ml) {
153         mac_learning_run(sw->ml, NULL);
154     }
155
156     /* If we're waiting for more replies, keeping waiting for up to 10 s. */
157     if (sw->last_reply != LLONG_MIN) {
158         if (now - sw->last_reply > 10000) {
159             VLOG_ERR_RL(&rl, "%016llx: No more flow stat replies last 10 s",
160                         sw->datapath_id);
161             sw->last_reply = LLONG_MIN;
162             sw->last_query = LLONG_MIN;
163             schedule_query(sw, 0);
164         } else {
165             return;
166         }
167     }
168
169     /* If we're waiting for any reply at all, keep waiting for up to 10 s. */
170     if (sw->last_query != LLONG_MIN) {
171         if (now - sw->last_query > 10000) {
172             VLOG_ERR_RL(&rl, "%016llx: No flow stat replies in last 10 s",
173                         sw->datapath_id);
174             sw->last_query = LLONG_MIN;
175             schedule_query(sw, 0);
176         } else {
177             return;
178         }
179     }
180
181     /* If it's time to send another query, do so. */
182     if (sw->next_query != LLONG_MIN && now >= sw->next_query) {
183         sw->next_query = LLONG_MIN;
184         if (!rconn_is_connected(rconn)) {
185             schedule_query(sw, 1000);
186         } else {
187             struct ofp_stats_request *osr;
188             struct ofp_flow_stats_request *ofsr;
189             struct ofpbuf *b;
190             int error;
191
192             VLOG_DBG("%016llx: Sending flow stats request to implement STP",
193                      sw->datapath_id);
194
195             sw->last_query = now;
196             sw->query_xid = random_uint32();
197             sw->n_flows = 0;
198             sw->n_no_recv = 0;
199             sw->n_no_send = 0;
200             osr = make_openflow_xid(sizeof *osr + sizeof *ofsr,
201                                     OFPT_STATS_REQUEST, sw->query_xid, &b);
202             osr->type = htons(OFPST_FLOW);
203             osr->flags = htons(0);
204             ofsr = (struct ofp_flow_stats_request *) osr->body;
205             ofsr->match.wildcards = htonl(OFPFW_ALL);
206             ofsr->table_id = 0xff;
207             ofsr->out_port = htons(OFPP_NONE);
208
209             error = rconn_send(rconn, b, NULL);
210             if (error) {
211                 VLOG_WARN_RL(&rl, "%016llx: sending flow stats request "
212                              "failed: %s", sw->datapath_id, strerror(error));
213                 ofpbuf_delete(b);
214                 schedule_query(sw, 1000);
215             }
216         }
217     }
218 }
219
220 static void
221 wait_timeout(long long int started)
222 {
223     long long int now = time_msec();
224     long long int timeout = 10000 - (now - started);
225     if (timeout <= 0) {
226         poll_immediate_wake();
227     } else {
228         poll_timer_wait(timeout);
229     }
230 }
231
232 void
233 lswitch_wait(struct lswitch *sw)
234 {
235     if (sw->ml) {
236         mac_learning_wait(sw->ml);
237     }
238
239     if (sw->last_reply != LLONG_MIN) {
240         wait_timeout(sw->last_reply);
241     } else if (sw->last_query != LLONG_MIN) {
242         wait_timeout(sw->last_query);
243     }
244 }
245
246 /* Processes 'msg', which should be an OpenFlow received on 'rconn', according
247  * to the learning switch state in 'sw'.  The most likely result of processing
248  * is that flow-setup and packet-out OpenFlow messages will be sent out on
249  * 'rconn'.  */
250 void
251 lswitch_process_packet(struct lswitch *sw, struct rconn *rconn,
252                        const struct ofpbuf *msg)
253 {
254     struct processor {
255         uint8_t type;
256         size_t min_size;
257         packet_handler_func *handler;
258     };
259     static const struct processor processors[] = {
260         {
261             OFPT_ECHO_REQUEST,
262             sizeof(struct ofp_header),
263             process_echo_request
264         },
265         {
266             OFPT_FEATURES_REPLY,
267             sizeof(struct ofp_switch_features),
268             process_switch_features
269         },
270         {
271             OFPT_PACKET_IN,
272             offsetof(struct ofp_packet_in, data),
273             process_packet_in
274         },
275         {
276             OFPT_PORT_STATUS,
277             sizeof(struct ofp_port_status),
278             process_port_status
279         },
280         {
281             OFPT_STATS_REPLY,
282             offsetof(struct ofp_stats_reply, body),
283             process_stats_reply
284         },
285         {
286             OFPT_FLOW_REMOVED,
287             sizeof(struct ofp_flow_removed),
288             NULL
289         },
290     };
291     const size_t n_processors = ARRAY_SIZE(processors);
292     const struct processor *p;
293     struct ofp_header *oh;
294
295     oh = msg->data;
296     if (sw->datapath_id == 0
297         && oh->type != OFPT_ECHO_REQUEST
298         && oh->type != OFPT_FEATURES_REPLY) {
299         send_features_request(sw, rconn);
300         return;
301     }
302
303     for (p = processors; p < &processors[n_processors]; p++) {
304         if (oh->type == p->type) {
305             if (msg->size < p->min_size) {
306                 VLOG_WARN_RL(&rl, "%016llx: %s: too short (%zu bytes) for "
307                              "type %"PRIu8" (min %zu)", sw->datapath_id,
308                              rconn_get_name(rconn), msg->size, oh->type,
309                              p->min_size);
310                 return;
311             }
312             if (p->handler) {
313                 (p->handler)(sw, rconn, msg->data);
314             }
315             return;
316         }
317     }
318     if (VLOG_IS_DBG_ENABLED()) {
319         char *p = ofp_to_string(msg->data, msg->size, 2);
320         VLOG_DBG_RL(&rl, "%016llx: OpenFlow packet ignored: %s",
321                     sw->datapath_id, p);
322         free(p);
323     }
324 }
325 \f
326 static void
327 send_features_request(struct lswitch *sw, struct rconn *rconn)
328 {
329     time_t now = time_now();
330     if (now >= sw->last_features_request + 1) {
331         struct ofpbuf *b;
332         struct ofp_switch_config *osc;
333
334         /* Send OFPT_FEATURES_REQUEST. */
335         make_openflow(sizeof(struct ofp_header), OFPT_FEATURES_REQUEST, &b);
336         queue_tx(sw, rconn, b);
337
338         /* Send OFPT_SET_CONFIG. */
339         osc = make_openflow(sizeof *osc, OFPT_SET_CONFIG, &b);
340         osc->miss_send_len = htons(OFP_DEFAULT_MISS_SEND_LEN);
341         queue_tx(sw, rconn, b);
342
343         sw->last_features_request = now;
344     }
345 }
346
347 static void
348 queue_tx(struct lswitch *sw, struct rconn *rconn, struct ofpbuf *b)
349 {
350     int retval = rconn_send_with_limit(rconn, b, sw->queued, 10);
351     if (retval && retval != ENOTCONN) {
352         if (retval == EAGAIN) {
353             VLOG_INFO_RL(&rl, "%016llx: %s: tx queue overflow",
354                          sw->datapath_id, rconn_get_name(rconn));
355         } else {
356             VLOG_WARN_RL(&rl, "%016llx: %s: send: %s",
357                          sw->datapath_id, rconn_get_name(rconn),
358                          strerror(retval));
359         }
360     }
361 }
362
363 static void
364 schedule_query(struct lswitch *sw, long long int delay)
365 {
366     long long int now = time_msec();
367     if (sw->next_query == LLONG_MIN || sw->next_query > now + delay) {
368         sw->next_query = now + delay;
369     }
370 }
371
372 static void
373 process_switch_features(struct lswitch *sw, struct rconn *rconn, void *osf_)
374 {
375     struct ofp_switch_features *osf = osf_;
376     size_t n_ports = ((ntohs(osf->header.length)
377                        - offsetof(struct ofp_switch_features, ports))
378                       / sizeof *osf->ports);
379     size_t i;
380
381     sw->datapath_id = ntohll(osf->datapath_id);
382     sw->capabilities = ntohl(osf->capabilities);
383     for (i = 0; i < n_ports; i++) {
384         process_phy_port(sw, rconn, &osf->ports[i]);
385     }
386     if (sw->capabilities & OFPC_STP) {
387         schedule_query(sw, 1000);
388     }
389 }
390
391 static void
392 process_packet_in(struct lswitch *sw, struct rconn *rconn, void *opi_)
393 {
394     struct ofp_packet_in *opi = opi_;
395     uint16_t in_port = ntohs(opi->in_port);
396     uint16_t out_port = OFPP_FLOOD;
397
398     size_t pkt_ofs, pkt_len;
399     struct ofpbuf pkt;
400     flow_t flow;
401
402     /* Extract flow data from 'opi' into 'flow'. */
403     pkt_ofs = offsetof(struct ofp_packet_in, data);
404     pkt_len = ntohs(opi->header.length) - pkt_ofs;
405     pkt.data = opi->data;
406     pkt.size = pkt_len;
407     flow_extract(&pkt, 0, in_port, &flow);
408
409     if (may_learn(sw, in_port) && sw->ml) {
410         if (mac_learning_learn(sw->ml, flow.dl_src, 0, in_port)) {
411             VLOG_DBG_RL(&rl, "%016llx: learned that "ETH_ADDR_FMT" is on "
412                         "port %"PRIu16, sw->datapath_id,
413                         ETH_ADDR_ARGS(flow.dl_src), in_port);
414         }
415     }
416
417     if (eth_addr_is_reserved(flow.dl_src)) {
418         goto drop_it;
419     }
420
421     if (!may_recv(sw, in_port, false)) {
422         /* STP prevents receiving anything on this port. */
423         goto drop_it;
424     }
425
426     if (sw->ml) {
427         int learned_port = mac_learning_lookup(sw->ml, flow.dl_dst, 0);
428         if (learned_port >= 0 && may_send(sw, learned_port)) {
429             out_port = learned_port;
430         }
431     }
432
433     if (in_port == out_port) {
434         /* Don't send out packets on their input ports. */
435         goto drop_it;
436     } else if (sw->max_idle >= 0 && (!sw->ml || out_port != OFPP_FLOOD)) {
437         struct ofpbuf *buffer;
438         struct ofp_flow_mod *ofm;
439         uint32_t wildcards;
440
441         /* Check if we need to wildcard the flows. */
442         if (!sw->exact_flows) {
443             /* We can not wildcard all fields.
444              * We need in_port to detect moves.
445              * We need both SA and DA to do learning. */
446             wildcards = (OFPFW_DL_TYPE | OFPFW_NW_SRC_MASK | OFPFW_NW_DST_MASK
447                          | OFPFW_NW_PROTO | OFPFW_TP_SRC | OFPFW_TP_DST);
448         } else {
449             /* Exact match */
450             wildcards = 0;
451         }
452
453         /* Check if we need to use "NORMAL" action. */
454         if (sw->action_normal && out_port != OFPP_FLOOD) {
455             out_port = OFPP_NORMAL;
456         }
457
458         /* The output port is known, or we always flood everything, so add a
459          * new flow. */
460         buffer = make_add_simple_flow(&flow, ntohl(opi->buffer_id),
461                                       out_port, sw->max_idle);
462         ofm = buffer->data;
463         ofm->match.wildcards = htonl(wildcards);
464         queue_tx(sw, rconn, buffer);
465
466         /* If the switch didn't buffer the packet, we need to send a copy. */
467         if (ntohl(opi->buffer_id) == UINT32_MAX) {
468             queue_tx(sw, rconn,
469                      make_unbuffered_packet_out(&pkt, in_port, out_port));
470         }
471     } else {
472         struct ofpbuf *b;
473
474         /* Check if we need to use "NORMAL" action. */
475         if (sw->action_normal && out_port != OFPP_FLOOD) {
476             out_port = OFPP_NORMAL;
477         }
478
479         /* We don't know that MAC, or we don't set up flows.  Send along the
480          * packet without setting up a flow. */
481         if (ntohl(opi->buffer_id) == UINT32_MAX) {
482             b = make_unbuffered_packet_out(&pkt, in_port, out_port);
483         } else {
484             b = make_buffered_packet_out(ntohl(opi->buffer_id),
485                                          in_port, out_port);
486         }
487         queue_tx(sw, rconn, b);
488     }
489     return;
490
491 drop_it:
492     if (sw->max_idle >= 0) {
493         /* Set up a flow to drop packets. */
494         queue_tx(sw, rconn, make_add_flow(&flow, ntohl(opi->buffer_id),
495                                           sw->max_idle, 0));
496     } else {
497         /* Just drop the packet, since we don't set up flows at all.
498          * XXX we should send a packet_out with no actions if buffer_id !=
499          * UINT32_MAX, to avoid clogging the kernel buffers. */
500     }
501     return;
502 }
503
504 static void
505 process_echo_request(struct lswitch *sw, struct rconn *rconn, void *rq_)
506 {
507     struct ofp_header *rq = rq_;
508     queue_tx(sw, rconn, make_echo_reply(rq));
509 }
510
511 static void
512 process_port_status(struct lswitch *sw, struct rconn *rconn, void *ops_)
513 {
514     struct ofp_port_status *ops = ops_;
515     process_phy_port(sw, rconn, &ops->desc);
516 }
517
518 static void
519 process_phy_port(struct lswitch *sw, struct rconn *rconn OVS_UNUSED,
520                  void *opp_)
521 {
522     const struct ofp_phy_port *opp = opp_;
523     uint16_t port_no = ntohs(opp->port_no);
524     if (sw->capabilities & OFPC_STP && port_no < STP_MAX_PORTS) {
525         uint32_t config = ntohl(opp->config);
526         uint32_t state = ntohl(opp->state);
527         unsigned int *port_state = &sw->port_states[port_no];
528         unsigned int new_port_state;
529
530         if (!(config & (OFPPC_NO_STP | OFPPC_PORT_DOWN))
531             && !(state & OFPPS_LINK_DOWN))
532         {
533             switch (state & OFPPS_STP_MASK) {
534             case OFPPS_STP_LISTEN:
535                 new_port_state = P_LISTENING;
536                 break;
537             case OFPPS_STP_LEARN:
538                 new_port_state = P_LEARNING;
539                 break;
540             case OFPPS_STP_FORWARD:
541                 new_port_state = P_FORWARDING;
542                 break;
543             case OFPPS_STP_BLOCK:
544                 new_port_state = P_BLOCKING;
545                 break;
546             default:
547                 new_port_state = P_DISABLED;
548                 break;
549             }
550         } else {
551             new_port_state = P_FORWARDING;
552         }
553         if (*port_state != new_port_state) {
554             *port_state = new_port_state;
555             schedule_query(sw, 1000);
556         }
557     }
558 }
559
560 static unsigned int
561 get_port_state(const struct lswitch *sw, uint16_t port_no)
562 {
563     return (port_no >= STP_MAX_PORTS || !(sw->capabilities & OFPC_STP)
564             ? P_FORWARDING
565             : sw->port_states[port_no]);
566 }
567
568 static bool
569 may_learn(const struct lswitch *sw, uint16_t port_no)
570 {
571     return get_port_state(sw, port_no) & (P_LEARNING | P_FORWARDING);
572 }
573
574 static bool
575 may_recv(const struct lswitch *sw, uint16_t port_no, bool any_actions)
576 {
577     unsigned int state = get_port_state(sw, port_no);
578     return !(any_actions
579              ? state & (P_DISABLED | P_LISTENING | P_BLOCKING)
580              : state & (P_DISABLED | P_LISTENING | P_BLOCKING | P_LEARNING));
581 }
582
583 static bool
584 may_send(const struct lswitch *sw, uint16_t port_no)
585 {
586     return get_port_state(sw, port_no) & P_FORWARDING;
587 }
588
589 static void
590 process_flow_stats(struct lswitch *sw, struct rconn *rconn,
591                    const struct ofp_flow_stats *ofs)
592 {
593     const char *end = (char *) ofs + ntohs(ofs->length);
594     bool delete = false;
595
596     /* Decide to delete the flow if it matches on an STP-disabled physical
597      * port.  But don't delete it if the flow just drops all received packets,
598      * because that's a perfectly reasonable thing to do for disabled physical
599      * ports. */
600     if (!(ofs->match.wildcards & htonl(OFPFW_IN_PORT))) {
601         if (!may_recv(sw, ntohs(ofs->match.in_port),
602                       end > (char *) ofs->actions)) {
603             delete = true;
604             sw->n_no_recv++;
605         }
606     }
607
608     /* Decide to delete the flow if it forwards to an STP-disabled physical
609      * port. */
610     if (!delete) {
611         const struct ofp_action_header *a;
612         size_t len;
613
614         for (a = ofs->actions; (char *) a < end; a += len / 8) {
615             len = ntohs(a->len);
616             if (len > end - (char *) a) {
617                 VLOG_DBG_RL(&rl, "%016llx: action exceeds available space "
618                             "(%zu > %td)",
619                             sw->datapath_id, len, end - (char *) a);
620                 break;
621             } else if (len % 8) {
622                 VLOG_DBG_RL(&rl, "%016llx: action length (%zu) not multiple "
623                             "of 8 bytes", sw->datapath_id, len);
624                 break;
625             }
626
627             if (a->type == htons(OFPAT_OUTPUT)) {
628                 struct ofp_action_output *oao = (struct ofp_action_output *) a;
629                 if (!may_send(sw, ntohs(oao->port))) {
630                     delete = true;
631                     sw->n_no_send++;
632                     break;
633                 }
634             }
635         }
636     }
637
638     /* Delete the flow. */
639     if (delete) {
640         struct ofp_flow_mod *ofm;
641         struct ofpbuf *b;
642
643         ofm = make_openflow(offsetof(struct ofp_flow_mod, actions),
644                             OFPT_FLOW_MOD, &b);
645         ofm->match = ofs->match;
646         ofm->command = OFPFC_DELETE_STRICT;
647         rconn_send(rconn, b, NULL);
648     }
649 }
650
651 static void
652 process_stats_reply(struct lswitch *sw, struct rconn *rconn, void *osr_)
653 {
654     struct ofp_stats_reply *osr = osr_;
655     struct flow_stats_iterator i;
656     const struct ofp_flow_stats *fs;
657
658     if (sw->last_query == LLONG_MIN
659         || osr->type != htons(OFPST_FLOW)
660         || osr->header.xid != sw->query_xid) {
661         return;
662     }
663     for (fs = flow_stats_first(&i, osr); fs; fs = flow_stats_next(&i)) {
664         sw->n_flows++;
665         process_flow_stats(sw, rconn, fs);
666     }
667     if (!(osr->flags & htons(OFPSF_REPLY_MORE))) {
668         VLOG_DBG("%016llx: Deleted %d of %d received flows to "
669                  "implement STP, %d because of no-recv, %d because of "
670                  "no-send", sw->datapath_id,
671                  sw->n_no_recv + sw->n_no_send, sw->n_flows,
672                  sw->n_no_recv, sw->n_no_send);
673         sw->last_query = LLONG_MIN;
674         sw->last_reply = LLONG_MIN;
675     } else {
676         sw->last_reply = time_msec();
677     }
678 }
679