lib/dpif-netdev.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "dpif.h"
  19
  20 #include <assert.h>
  21 #include <ctype.h>
  22 #include <errno.h>
  23 #include <fcntl.h>
  24 #include <inttypes.h>
  25 #include <netinet/in.h>
  26 #include <sys/socket.h>
  27 #include <net/if.h>
  28 #include <stdint.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <sys/ioctl.h>
  32 #include <sys/stat.h>
  33 #include <unistd.h>
  34
  35 #include "csum.h"
  36 #include "dpif.h"
  37 #include "dpif-provider.h"
  38 #include "dummy.h"
  39 #include "dynamic-string.h"
  40 #include "flow.h"
  41 #include "hmap.h"
  42 #include "list.h"
  43 #include "netdev.h"
  44 #include "netlink.h"
  45 #include "odp-util.h"
  46 #include "ofp-print.h"
  47 #include "ofpbuf.h"
  48 #include "packets.h"
  49 #include "poll-loop.h"
  50 #include "random.h"
  51 #include "shash.h"
  52 #include "timeval.h"
  53 #include "util.h"
  54 #include "vlog.h"
  55
  56 VLOG_DEFINE_THIS_MODULE(dpif_netdev);
  57
  58 /* Configuration parameters. */
  59 enum { MAX_PORTS = 256 };       /* Maximum number of ports. */
  60 enum { MAX_FLOWS = 65536 };     /* Maximum number of flows in flow table. */
  61
  62 /* Enough headroom to add a vlan tag, plus an extra 2 bytes to allow IP
  63  * headers to be aligned on a 4-byte boundary.  */
  64 enum { DP_NETDEV_HEADROOM = 2 + VLAN_HEADER_LEN };
  65
  66 /* Queues. */
  67 enum { N_QUEUES = 2 };          /* Number of queues for dpif_recv(). */
  68 enum { MAX_QUEUE_LEN = 128 };   /* Maximum number of packets per queue. */
  69 enum { QUEUE_MASK = MAX_QUEUE_LEN - 1 };
  70 BUILD_ASSERT_DECL(IS_POW2(MAX_QUEUE_LEN));
  71
  72 struct dp_netdev_queue {
  73     struct dpif_upcall *upcalls[MAX_QUEUE_LEN];
  74     unsigned int head, tail;
  75 };
  76
  77 /* Datapath based on the network device interface from netdev.h. */
  78 struct dp_netdev {
  79     const struct dpif_class *class;
  80     char *name;
  81     int open_cnt;
  82     bool destroyed;
  83
  84     bool drop_frags;            /* Drop all IP fragments, if true. */
  85     struct dp_netdev_queue queues[N_QUEUES];
  86     struct hmap flow_table;     /* Flow table. */
  87
  88     /* Statistics. */
  89     long long int n_frags;      /* Number of dropped IP fragments. */
  90     long long int n_hit;        /* Number of flow table matches. */
  91     long long int n_missed;     /* Number of flow table misses. */
  92     long long int n_lost;       /* Number of misses not passed to client. */
  93
  94     /* Ports. */
  95     struct dp_netdev_port *ports[MAX_PORTS];
  96     struct list port_list;
  97     unsigned int serial;
  98 };
  99
 100 /* A port in a netdev-based datapath. */
 101 struct dp_netdev_port {
 102     int port_no;                /* Index into dp_netdev's 'ports'. */
 103     struct list node;           /* Element in dp_netdev's 'port_list'. */
 104     struct netdev *netdev;
 105     bool internal;              /* Internal port? */
 106 };
 107
 108 /* A flow in dp_netdev's 'flow_table'. */
 109 struct dp_netdev_flow {
 110     struct hmap_node node;      /* Element in dp_netdev's 'flow_table'. */
 111     struct flow key;
 112
 113     /* Statistics. */
 114     long long int used;         /* Last used time, in monotonic msecs. */
 115     long long int packet_count; /* Number of packets matched. */
 116     long long int byte_count;   /* Number of bytes matched. */
 117     ovs_be16 tcp_ctl;           /* Bitwise-OR of seen tcp_ctl values. */
 118
 119     /* Actions. */
 120     struct nlattr *actions;
 121     size_t actions_len;
 122 };
 123
 124 /* Interface to netdev-based datapath. */
 125 struct dpif_netdev {
 126     struct dpif dpif;
 127     struct dp_netdev *dp;
 128     int listen_mask;
 129     unsigned int dp_serial;
 130 };
 131
 132 /* All netdev-based datapaths. */
 133 static struct shash dp_netdevs = SHASH_INITIALIZER(&dp_netdevs);
 134
 135 /* Maximum port MTU seen so far. */
 136 static int max_mtu = ETH_PAYLOAD_MAX;
 137
 138 static int get_port_by_number(struct dp_netdev *, uint16_t port_no,
 139                               struct dp_netdev_port **portp);
 140 static int get_port_by_name(struct dp_netdev *, const char *devname,
 141                             struct dp_netdev_port **portp);
 142 static void dp_netdev_free(struct dp_netdev *);
 143 static void dp_netdev_flow_flush(struct dp_netdev *);
 144 static int do_add_port(struct dp_netdev *, const char *devname,
 145                        const char *type, uint16_t port_no);
 146 static int do_del_port(struct dp_netdev *, uint16_t port_no);
 147 static int dpif_netdev_open(const struct dpif_class *, const char *name,
 148                             bool create, struct dpif **);
 149 static int dp_netdev_output_userspace(struct dp_netdev *, const struct ofpbuf *,
 150                                     int queue_no, const struct flow *,
 151                                     uint64_t arg);
 152 static int dp_netdev_execute_actions(struct dp_netdev *,
 153                                      struct ofpbuf *, struct flow *,
 154                                      const struct nlattr *actions,
 155                                      size_t actions_len);
 156
 157 static struct dpif_class dpif_dummy_class;
 158
 159 static struct dpif_netdev *
 160 dpif_netdev_cast(const struct dpif *dpif)
 161 {
 162     assert(dpif->dpif_class->open == dpif_netdev_open);
 163     return CONTAINER_OF(dpif, struct dpif_netdev, dpif);
 164 }
 165
 166 static struct dp_netdev *
 167 get_dp_netdev(const struct dpif *dpif)
 168 {
 169     return dpif_netdev_cast(dpif)->dp;
 170 }
 171
 172 static struct dpif *
 173 create_dpif_netdev(struct dp_netdev *dp)
 174 {
 175     uint16_t netflow_id = hash_string(dp->name, 0);
 176     struct dpif_netdev *dpif;
 177
 178     dp->open_cnt++;
 179
 180     dpif = xmalloc(sizeof *dpif);
 181     dpif_init(&dpif->dpif, dp->class, dp->name, netflow_id >> 8, netflow_id);
 182     dpif->dp = dp;
 183     dpif->listen_mask = 0;
 184     dpif->dp_serial = dp->serial;
 185
 186     return &dpif->dpif;
 187 }
 188
 189 static int
 190 create_dp_netdev(const char *name, const struct dpif_class *class,
 191                  struct dp_netdev **dpp)
 192 {
 193     struct dp_netdev *dp;
 194     int error;
 195     int i;
 196
 197     dp = xzalloc(sizeof *dp);
 198     dp->class = class;
 199     dp->name = xstrdup(name);
 200     dp->open_cnt = 0;
 201     dp->drop_frags = false;
 202     for (i = 0; i < N_QUEUES; i++) {
 203         dp->queues[i].head = dp->queues[i].tail = 0;
 204     }
 205     hmap_init(&dp->flow_table);
 206     list_init(&dp->port_list);
 207     error = do_add_port(dp, name, "internal", OVSP_LOCAL);
 208     if (error) {
 209         dp_netdev_free(dp);
 210         return error;
 211     }
 212
 213     shash_add(&dp_netdevs, name, dp);
 214
 215     *dpp = dp;
 216     return 0;
 217 }
 218
 219 static int
 220 dpif_netdev_open(const struct dpif_class *class, const char *name,
 221                  bool create, struct dpif **dpifp)
 222 {
 223     struct dp_netdev *dp;
 224
 225     dp = shash_find_data(&dp_netdevs, name);
 226     if (!dp) {
 227         if (!create) {
 228             return ENODEV;
 229         } else {
 230             int error = create_dp_netdev(name, class, &dp);
 231             if (error) {
 232                 return error;
 233             }
 234             assert(dp != NULL);
 235         }
 236     } else {
 237         if (dp->class != class) {
 238             return EINVAL;
 239         } else if (create) {
 240             return EEXIST;
 241         }
 242     }
 243
 244     *dpifp = create_dpif_netdev(dp);
 245     return 0;
 246 }
 247
 248 static void
 249 dp_netdev_purge_queues(struct dp_netdev *dp)
 250 {
 251     int i;
 252
 253     for (i = 0; i < N_QUEUES; i++) {
 254         struct dp_netdev_queue *q = &dp->queues[i];
 255
 256         while (q->tail != q->head) {
 257             struct dpif_upcall *upcall = q->upcalls[q->tail++ & QUEUE_MASK];
 258
 259             ofpbuf_delete(upcall->packet);
 260             free(upcall);
 261         }
 262     }
 263 }
 264
 265 static void
 266 dp_netdev_free(struct dp_netdev *dp)
 267 {
 268     struct dp_netdev_port *port, *next;
 269
 270     dp_netdev_flow_flush(dp);
 271     LIST_FOR_EACH_SAFE (port, next, node, &dp->port_list) {
 272         do_del_port(dp, port->port_no);
 273     }
 274     dp_netdev_purge_queues(dp);
 275     hmap_destroy(&dp->flow_table);
 276     free(dp->name);
 277     free(dp);
 278 }
 279
 280 static void
 281 dpif_netdev_close(struct dpif *dpif)
 282 {
 283     struct dp_netdev *dp = get_dp_netdev(dpif);
 284     assert(dp->open_cnt > 0);
 285     if (--dp->open_cnt == 0 && dp->destroyed) {
 286         shash_find_and_delete(&dp_netdevs, dp->name);
 287         dp_netdev_free(dp);
 288     }
 289     free(dpif);
 290 }
 291
 292 static int
 293 dpif_netdev_destroy(struct dpif *dpif)
 294 {
 295     struct dp_netdev *dp = get_dp_netdev(dpif);
 296     dp->destroyed = true;
 297     return 0;
 298 }
 299
 300 static int
 301 dpif_netdev_get_stats(const struct dpif *dpif, struct dpif_dp_stats *stats)
 302 {
 303     struct dp_netdev *dp = get_dp_netdev(dpif);
 304     stats->n_flows = hmap_count(&dp->flow_table);
 305     stats->n_frags = dp->n_frags;
 306     stats->n_hit = dp->n_hit;
 307     stats->n_missed = dp->n_missed;
 308     stats->n_lost = dp->n_lost;
 309     return 0;
 310 }
 311
 312 static int
 313 dpif_netdev_get_drop_frags(const struct dpif *dpif, bool *drop_fragsp)
 314 {
 315     struct dp_netdev *dp = get_dp_netdev(dpif);
 316     *drop_fragsp = dp->drop_frags;
 317     return 0;
 318 }
 319
 320 static int
 321 dpif_netdev_set_drop_frags(struct dpif *dpif, bool drop_frags)
 322 {
 323     struct dp_netdev *dp = get_dp_netdev(dpif);
 324     dp->drop_frags = drop_frags;
 325     return 0;
 326 }
 327
 328 static int
 329 do_add_port(struct dp_netdev *dp, const char *devname, const char *type,
 330             uint16_t port_no)
 331 {
 332     struct dp_netdev_port *port;
 333     struct netdev *netdev;
 334     bool internal;
 335     int mtu;
 336     int error;
 337
 338     /* XXX reject devices already in some dp_netdev. */
 339     if (type[0] == '\0' || !strcmp(type, "system") || !strcmp(type, "dummy")) {
 340         internal = false;
 341     } else if (!strcmp(type, "internal")) {
 342         internal = true;
 343     } else {
 344         VLOG_WARN("%s: unsupported port type %s", devname, type);
 345         return EINVAL;
 346     }
 347
 348     /* Open and validate network device. */
 349     if (dp->class == &dpif_dummy_class) {
 350         type = "dummy";
 351     } else if (internal) {
 352         type = "tap";
 353     }
 354
 355     error = netdev_open(devname, type, &netdev);
 356     if (error) {
 357         return error;
 358     }
 359     /* XXX reject loopback devices */
 360     /* XXX reject non-Ethernet devices */
 361
 362     error = netdev_listen(netdev);
 363     if (error) {
 364         VLOG_ERR("%s: cannot receive packets on this network device (%s)",
 365                  devname, strerror(errno));
 366         netdev_close(netdev);
 367         return error;
 368     }
 369
 370     error = netdev_turn_flags_on(netdev, NETDEV_PROMISC, false);
 371     if (error) {
 372         netdev_close(netdev);
 373         return error;
 374     }
 375
 376     port = xmalloc(sizeof *port);
 377     port->port_no = port_no;
 378     port->netdev = netdev;
 379     port->internal = internal;
 380
 381     error = netdev_get_mtu(netdev, &mtu);
 382     if (!error) {
 383         max_mtu = mtu;
 384     }
 385
 386     list_push_back(&dp->port_list, &port->node);
 387     dp->ports[port_no] = port;
 388     dp->serial++;
 389
 390     return 0;
 391 }
 392
 393 static int
 394 dpif_netdev_port_add(struct dpif *dpif, struct netdev *netdev,
 395                      uint16_t *port_nop)
 396 {
 397     struct dp_netdev *dp = get_dp_netdev(dpif);
 398     int port_no;
 399
 400     for (port_no = 0; port_no < MAX_PORTS; port_no++) {
 401         if (!dp->ports[port_no]) {
 402             *port_nop = port_no;
 403             return do_add_port(dp, netdev_get_name(netdev),
 404                                netdev_get_type(netdev), port_no);
 405         }
 406     }
 407     return EFBIG;
 408 }
 409
 410 static int
 411 dpif_netdev_port_del(struct dpif *dpif, uint16_t port_no)
 412 {
 413     struct dp_netdev *dp = get_dp_netdev(dpif);
 414     return port_no == OVSP_LOCAL ? EINVAL : do_del_port(dp, port_no);
 415 }
 416
 417 static bool
 418 is_valid_port_number(uint16_t port_no)
 419 {
 420     return port_no < MAX_PORTS;
 421 }
 422
 423 static int
 424 get_port_by_number(struct dp_netdev *dp,
 425                    uint16_t port_no, struct dp_netdev_port **portp)
 426 {
 427     if (!is_valid_port_number(port_no)) {
 428         *portp = NULL;
 429         return EINVAL;
 430     } else {
 431         *portp = dp->ports[port_no];
 432         return *portp ? 0 : ENOENT;
 433     }
 434 }
 435
 436 static int
 437 get_port_by_name(struct dp_netdev *dp,
 438                  const char *devname, struct dp_netdev_port **portp)
 439 {
 440     struct dp_netdev_port *port;
 441
 442     LIST_FOR_EACH (port, node, &dp->port_list) {
 443         if (!strcmp(netdev_get_name(port->netdev), devname)) {
 444             *portp = port;
 445             return 0;
 446         }
 447     }
 448     return ENOENT;
 449 }
 450
 451 static int
 452 do_del_port(struct dp_netdev *dp, uint16_t port_no)
 453 {
 454     struct dp_netdev_port *port;
 455     char *name;
 456     int error;
 457
 458     error = get_port_by_number(dp, port_no, &port);
 459     if (error) {
 460         return error;
 461     }
 462
 463     list_remove(&port->node);
 464     dp->ports[port->port_no] = NULL;
 465     dp->serial++;
 466
 467     name = xstrdup(netdev_get_name(port->netdev));
 468     netdev_close(port->netdev);
 469
 470     free(name);
 471     free(port);
 472
 473     return 0;
 474 }
 475
 476 static void
 477 answer_port_query(const struct dp_netdev_port *port,
 478                   struct dpif_port *dpif_port)
 479 {
 480     dpif_port->name = xstrdup(netdev_get_name(port->netdev));
 481     dpif_port->type = xstrdup(port->internal ? "internal" : "system");
 482     dpif_port->port_no = port->port_no;
 483 }
 484
 485 static int
 486 dpif_netdev_port_query_by_number(const struct dpif *dpif, uint16_t port_no,
 487                                  struct dpif_port *dpif_port)
 488 {
 489     struct dp_netdev *dp = get_dp_netdev(dpif);
 490     struct dp_netdev_port *port;
 491     int error;
 492
 493     error = get_port_by_number(dp, port_no, &port);
 494     if (!error) {
 495         answer_port_query(port, dpif_port);
 496     }
 497     return error;
 498 }
 499
 500 static int
 501 dpif_netdev_port_query_by_name(const struct dpif *dpif, const char *devname,
 502                                struct dpif_port *dpif_port)
 503 {
 504     struct dp_netdev *dp = get_dp_netdev(dpif);
 505     struct dp_netdev_port *port;
 506     int error;
 507
 508     error = get_port_by_name(dp, devname, &port);
 509     if (!error) {
 510         answer_port_query(port, dpif_port);
 511     }
 512     return error;
 513 }
 514
 515 static int
 516 dpif_netdev_get_max_ports(const struct dpif *dpif OVS_UNUSED)
 517 {
 518     return MAX_PORTS;
 519 }
 520
 521 static void
 522 dp_netdev_free_flow(struct dp_netdev *dp, struct dp_netdev_flow *flow)
 523 {
 524     hmap_remove(&dp->flow_table, &flow->node);
 525     free(flow->actions);
 526     free(flow);
 527 }
 528
 529 static void
 530 dp_netdev_flow_flush(struct dp_netdev *dp)
 531 {
 532     struct dp_netdev_flow *flow, *next;
 533
 534     HMAP_FOR_EACH_SAFE (flow, next, node, &dp->flow_table) {
 535         dp_netdev_free_flow(dp, flow);
 536     }
 537 }
 538
 539 static int
 540 dpif_netdev_flow_flush(struct dpif *dpif)
 541 {
 542     struct dp_netdev *dp = get_dp_netdev(dpif);
 543     dp_netdev_flow_flush(dp);
 544     return 0;
 545 }
 546
 547 struct dp_netdev_port_state {
 548     uint32_t port_no;
 549     char *name;
 550 };
 551
 552 static int
 553 dpif_netdev_port_dump_start(const struct dpif *dpif OVS_UNUSED, void **statep)
 554 {
 555     *statep = xzalloc(sizeof(struct dp_netdev_port_state));
 556     return 0;
 557 }
 558
 559 static int
 560 dpif_netdev_port_dump_next(const struct dpif *dpif, void *state_,
 561                            struct dpif_port *dpif_port)
 562 {
 563     struct dp_netdev_port_state *state = state_;
 564     struct dp_netdev *dp = get_dp_netdev(dpif);
 565     uint32_t port_no;
 566
 567     for (port_no = state->port_no; port_no < MAX_PORTS; port_no++) {
 568         struct dp_netdev_port *port = dp->ports[port_no];
 569         if (port) {
 570             free(state->name);
 571             state->name = xstrdup(netdev_get_name(port->netdev));
 572             dpif_port->name = state->name;
 573             dpif_port->type = port->internal ? "internal" : "system";
 574             dpif_port->port_no = port->port_no;
 575             state->port_no = port_no + 1;
 576             return 0;
 577         }
 578     }
 579     return EOF;
 580 }
 581
 582 static int
 583 dpif_netdev_port_dump_done(const struct dpif *dpif OVS_UNUSED, void *state_)
 584 {
 585     struct dp_netdev_port_state *state = state_;
 586     free(state->name);
 587     free(state);
 588     return 0;
 589 }
 590
 591 static int
 592 dpif_netdev_port_poll(const struct dpif *dpif_, char **devnamep OVS_UNUSED)
 593 {
 594     struct dpif_netdev *dpif = dpif_netdev_cast(dpif_);
 595     if (dpif->dp_serial != dpif->dp->serial) {
 596         dpif->dp_serial = dpif->dp->serial;
 597         return ENOBUFS;
 598     } else {
 599         return EAGAIN;
 600     }
 601 }
 602
 603 static void
 604 dpif_netdev_port_poll_wait(const struct dpif *dpif_)
 605 {
 606     struct dpif_netdev *dpif = dpif_netdev_cast(dpif_);
 607     if (dpif->dp_serial != dpif->dp->serial) {
 608         poll_immediate_wake();
 609     }
 610 }
 611
 612 static struct dp_netdev_flow *
 613 dp_netdev_lookup_flow(const struct dp_netdev *dp, const struct flow *key)
 614 {
 615     struct dp_netdev_flow *flow;
 616
 617     HMAP_FOR_EACH_WITH_HASH (flow, node, flow_hash(key, 0), &dp->flow_table) {
 618         if (flow_equal(&flow->key, key)) {
 619             return flow;
 620         }
 621     }
 622     return NULL;
 623 }
 624
 625 static void
 626 get_dpif_flow_stats(struct dp_netdev_flow *flow, struct dpif_flow_stats *stats)
 627 {
 628     stats->n_packets = flow->packet_count;
 629     stats->n_bytes = flow->byte_count;
 630     stats->used = flow->used;
 631     stats->tcp_flags = TCP_FLAGS(flow->tcp_ctl);
 632 }
 633
 634 static int
 635 dpif_netdev_flow_from_nlattrs(const struct nlattr *key, uint32_t key_len,
 636                               struct flow *flow)
 637 {
 638     if (odp_flow_key_to_flow(key, key_len, flow)) {
 639         /* This should not happen: it indicates that odp_flow_key_from_flow()
 640          * and odp_flow_key_to_flow() disagree on the acceptable form of a
 641          * flow.  Log the problem as an error, with enough details to enable
 642          * debugging. */
 643         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
 644
 645         if (!VLOG_DROP_ERR(&rl)) {
 646             struct ds s;
 647
 648             ds_init(&s);
 649             odp_flow_key_format(key, key_len, &s);
 650             VLOG_ERR("internal error parsing flow key %s", ds_cstr(&s));
 651             ds_destroy(&s);
 652         }
 653
 654         return EINVAL;
 655     }
 656
 657     if (flow->in_port < OFPP_MAX
 658         ? flow->in_port >= MAX_PORTS
 659         : flow->in_port != OFPP_LOCAL && flow->in_port != OFPP_NONE) {
 660         return EINVAL;
 661     }
 662
 663     return 0;
 664 }
 665
 666 static int
 667 dpif_netdev_flow_get(const struct dpif *dpif,
 668                      const struct nlattr *nl_key, size_t nl_key_len,
 669                      struct ofpbuf **actionsp, struct dpif_flow_stats *stats)
 670 {
 671     struct dp_netdev *dp = get_dp_netdev(dpif);
 672     struct dp_netdev_flow *flow;
 673     struct flow key;
 674     int error;
 675
 676     error = dpif_netdev_flow_from_nlattrs(nl_key, nl_key_len, &key);
 677     if (error) {
 678         return error;
 679     }
 680
 681     flow = dp_netdev_lookup_flow(dp, &key);
 682     if (!flow) {
 683         return ENOENT;
 684     }
 685
 686     if (stats) {
 687         get_dpif_flow_stats(flow, stats);
 688     }
 689     if (actionsp) {
 690         *actionsp = ofpbuf_clone_data(flow->actions, flow->actions_len);
 691     }
 692     return 0;
 693 }
 694
 695 static int
 696 set_flow_actions(struct dp_netdev_flow *flow,
 697                  const struct nlattr *actions, size_t actions_len)
 698 {
 699     flow->actions = xrealloc(flow->actions, actions_len);
 700     flow->actions_len = actions_len;
 701     memcpy(flow->actions, actions, actions_len);
 702     return 0;
 703 }
 704
 705 static int
 706 add_flow(struct dpif *dpif, const struct flow *key,
 707          const struct nlattr *actions, size_t actions_len)
 708 {
 709     struct dp_netdev *dp = get_dp_netdev(dpif);
 710     struct dp_netdev_flow *flow;
 711     int error;
 712
 713     flow = xzalloc(sizeof *flow);
 714     flow->key = *key;
 715
 716     error = set_flow_actions(flow, actions, actions_len);
 717     if (error) {
 718         free(flow);
 719         return error;
 720     }
 721
 722     hmap_insert(&dp->flow_table, &flow->node, flow_hash(&flow->key, 0));
 723     return 0;
 724 }
 725
 726 static void
 727 clear_stats(struct dp_netdev_flow *flow)
 728 {
 729     flow->used = 0;
 730     flow->packet_count = 0;
 731     flow->byte_count = 0;
 732     flow->tcp_ctl = 0;
 733 }
 734
 735 static int
 736 dpif_netdev_flow_put(struct dpif *dpif, enum dpif_flow_put_flags flags,
 737                     const struct nlattr *nl_key, size_t nl_key_len,
 738                     const struct nlattr *actions, size_t actions_len,
 739                     struct dpif_flow_stats *stats)
 740 {
 741     struct dp_netdev *dp = get_dp_netdev(dpif);
 742     struct dp_netdev_flow *flow;
 743     struct flow key;
 744     int error;
 745
 746     error = dpif_netdev_flow_from_nlattrs(nl_key, nl_key_len, &key);
 747     if (error) {
 748         return error;
 749     }
 750
 751     flow = dp_netdev_lookup_flow(dp, &key);
 752     if (!flow) {
 753         if (flags & DPIF_FP_CREATE) {
 754             if (hmap_count(&dp->flow_table) < MAX_FLOWS) {
 755                 if (stats) {
 756                     memset(stats, 0, sizeof *stats);
 757                 }
 758                 return add_flow(dpif, &key, actions, actions_len);
 759             } else {
 760                 return EFBIG;
 761             }
 762         } else {
 763             return ENOENT;
 764         }
 765     } else {
 766         if (flags & DPIF_FP_MODIFY) {
 767             int error = set_flow_actions(flow, actions, actions_len);
 768             if (!error) {
 769                 if (stats) {
 770                     get_dpif_flow_stats(flow, stats);
 771                 }
 772                 if (flags & DPIF_FP_ZERO_STATS) {
 773                     clear_stats(flow);
 774                 }
 775             }
 776             return error;
 777         } else {
 778             return EEXIST;
 779         }
 780     }
 781 }
 782
 783 static int
 784 dpif_netdev_flow_del(struct dpif *dpif,
 785                      const struct nlattr *nl_key, size_t nl_key_len,
 786                      struct dpif_flow_stats *stats)
 787 {
 788     struct dp_netdev *dp = get_dp_netdev(dpif);
 789     struct dp_netdev_flow *flow;
 790     struct flow key;
 791     int error;
 792
 793     error = dpif_netdev_flow_from_nlattrs(nl_key, nl_key_len, &key);
 794     if (error) {
 795         return error;
 796     }
 797
 798     flow = dp_netdev_lookup_flow(dp, &key);
 799     if (flow) {
 800         if (stats) {
 801             get_dpif_flow_stats(flow, stats);
 802         }
 803         dp_netdev_free_flow(dp, flow);
 804         return 0;
 805     } else {
 806         return ENOENT;
 807     }
 808 }
 809
 810 struct dp_netdev_flow_state {
 811     uint32_t bucket;
 812     uint32_t offset;
 813     struct nlattr *actions;
 814     struct odputil_keybuf keybuf;
 815     struct dpif_flow_stats stats;
 816 };
 817
 818 static int
 819 dpif_netdev_flow_dump_start(const struct dpif *dpif OVS_UNUSED, void **statep)
 820 {
 821     struct dp_netdev_flow_state *state;
 822
 823     *statep = state = xmalloc(sizeof *state);
 824     state->bucket = 0;
 825     state->offset = 0;
 826     state->actions = NULL;
 827     return 0;
 828 }
 829
 830 static int
 831 dpif_netdev_flow_dump_next(const struct dpif *dpif, void *state_,
 832                            const struct nlattr **key, size_t *key_len,
 833                            const struct nlattr **actions, size_t *actions_len,
 834                            const struct dpif_flow_stats **stats)
 835 {
 836     struct dp_netdev_flow_state *state = state_;
 837     struct dp_netdev *dp = get_dp_netdev(dpif);
 838     struct dp_netdev_flow *flow;
 839     struct hmap_node *node;
 840
 841     node = hmap_at_position(&dp->flow_table, &state->bucket, &state->offset);
 842     if (!node) {
 843         return EOF;
 844     }
 845
 846     flow = CONTAINER_OF(node, struct dp_netdev_flow, node);
 847
 848     if (key) {
 849         struct ofpbuf buf;
 850
 851         ofpbuf_use_stack(&buf, &state->keybuf, sizeof state->keybuf);
 852         odp_flow_key_from_flow(&buf, &flow->key);
 853
 854         *key = buf.data;
 855         *key_len = buf.size;
 856     }
 857
 858     if (actions) {
 859         free(state->actions);
 860         state->actions = xmemdup(flow->actions, flow->actions_len);
 861
 862         *actions = state->actions;
 863         *actions_len = flow->actions_len;
 864     }
 865
 866     if (stats) {
 867         get_dpif_flow_stats(flow, &state->stats);
 868         *stats = &state->stats;
 869     }
 870
 871     return 0;
 872 }
 873
 874 static int
 875 dpif_netdev_flow_dump_done(const struct dpif *dpif OVS_UNUSED, void *state_)
 876 {
 877     struct dp_netdev_flow_state *state = state_;
 878
 879     free(state->actions);
 880     free(state);
 881     return 0;
 882 }
 883
 884 static int
 885 dpif_netdev_execute(struct dpif *dpif,
 886                     const struct nlattr *key_attrs, size_t key_len,
 887                     const struct nlattr *actions, size_t actions_len,
 888                     const struct ofpbuf *packet)
 889 {
 890     struct dp_netdev *dp = get_dp_netdev(dpif);
 891     struct ofpbuf copy;
 892     struct flow key;
 893     int error;
 894
 895     if (packet->size < ETH_HEADER_LEN || packet->size > UINT16_MAX) {
 896         return EINVAL;
 897     }
 898
 899     /* Make a deep copy of 'packet', because we might modify its data. */
 900     ofpbuf_init(&copy, DP_NETDEV_HEADROOM + packet->size);
 901     ofpbuf_reserve(&copy, DP_NETDEV_HEADROOM);
 902     ofpbuf_put(&copy, packet->data, packet->size);
 903
 904     flow_extract(&copy, 0, -1, &key);
 905     error = dpif_netdev_flow_from_nlattrs(key_attrs, key_len, &key);
 906     if (!error) {
 907         error = dp_netdev_execute_actions(dp, &copy, &key,
 908                                           actions, actions_len);
 909     }
 910
 911     ofpbuf_uninit(&copy);
 912     return error;
 913 }
 914
 915 static int
 916 dpif_netdev_recv_get_mask(const struct dpif *dpif, int *listen_mask)
 917 {
 918     struct dpif_netdev *dpif_netdev = dpif_netdev_cast(dpif);
 919     *listen_mask = dpif_netdev->listen_mask;
 920     return 0;
 921 }
 922
 923 static int
 924 dpif_netdev_recv_set_mask(struct dpif *dpif, int listen_mask)
 925 {
 926     struct dpif_netdev *dpif_netdev = dpif_netdev_cast(dpif);
 927     dpif_netdev->listen_mask = listen_mask;
 928     return 0;
 929 }
 930
 931 static struct dp_netdev_queue *
 932 find_nonempty_queue(struct dpif *dpif)
 933 {
 934     struct dpif_netdev *dpif_netdev = dpif_netdev_cast(dpif);
 935     struct dp_netdev *dp = get_dp_netdev(dpif);
 936     int mask = dpif_netdev->listen_mask;
 937     int i;
 938
 939     for (i = 0; i < N_QUEUES; i++) {
 940         struct dp_netdev_queue *q = &dp->queues[i];
 941         if (q->head != q->tail && mask & (1u << i)) {
 942             return q;
 943         }
 944     }
 945     return NULL;
 946 }
 947
 948 static int
 949 dpif_netdev_recv(struct dpif *dpif, struct dpif_upcall *upcall)
 950 {
 951     struct dp_netdev_queue *q = find_nonempty_queue(dpif);
 952     if (q) {
 953         struct dpif_upcall *u = q->upcalls[q->tail++ & QUEUE_MASK];
 954         *upcall = *u;
 955         free(u);
 956
 957         return 0;
 958     } else {
 959         return EAGAIN;
 960     }
 961 }
 962
 963 static void
 964 dpif_netdev_recv_wait(struct dpif *dpif)
 965 {
 966     if (find_nonempty_queue(dpif)) {
 967         poll_immediate_wake();
 968     } else {
 969         /* No messages ready to be received, and dp_wait() will ensure that we
 970          * wake up to queue new messages, so there is nothing to do. */
 971     }
 972 }
 973
 974 static void
 975 dpif_netdev_recv_purge(struct dpif *dpif)
 976 {
 977     struct dpif_netdev *dpif_netdev = dpif_netdev_cast(dpif);
 978     dp_netdev_purge_queues(dpif_netdev->dp);
 979 }
 980 \f
 981 static void
 982 dp_netdev_flow_used(struct dp_netdev_flow *flow, struct flow *key,
 983                     const struct ofpbuf *packet)
 984 {
 985     flow->used = time_msec();
 986     flow->packet_count++;
 987     flow->byte_count += packet->size;
 988     if (key->dl_type == htons(ETH_TYPE_IP) && key->nw_proto == IPPROTO_TCP) {
 989         struct tcp_header *th = packet->l4;
 990         flow->tcp_ctl |= th->tcp_ctl;
 991     }
 992 }
 993
 994 static void
 995 dp_netdev_port_input(struct dp_netdev *dp, struct dp_netdev_port *port,
 996                      struct ofpbuf *packet)
 997 {
 998     struct dp_netdev_flow *flow;
 999     struct flow key;
1000
1001     if (packet->size < ETH_HEADER_LEN) {
1002         return;
1003     }
1004     if (flow_extract(packet, 0, port->port_no, &key) && dp->drop_frags) {
1005         dp->n_frags++;
1006         return;
1007     }
1008
1009     flow = dp_netdev_lookup_flow(dp, &key);
1010     if (flow) {
1011         dp_netdev_flow_used(flow, &key, packet);
1012         dp_netdev_execute_actions(dp, packet, &key,
1013                                   flow->actions, flow->actions_len);
1014         dp->n_hit++;
1015     } else {
1016         dp->n_missed++;
1017         dp_netdev_output_userspace(dp, packet, DPIF_UC_MISS, &key, 0);
1018     }
1019 }
1020
1021 static void
1022 dpif_netdev_run(struct dpif *dpif)
1023 {
1024     struct dp_netdev *dp = get_dp_netdev(dpif);
1025     struct dp_netdev_port *port;
1026     struct ofpbuf packet;
1027
1028     ofpbuf_init(&packet, DP_NETDEV_HEADROOM + VLAN_ETH_HEADER_LEN + max_mtu);
1029
1030     LIST_FOR_EACH (port, node, &dp->port_list) {
1031         int error;
1032
1033         /* Reset packet contents. */
1034         ofpbuf_clear(&packet);
1035         ofpbuf_reserve(&packet, DP_NETDEV_HEADROOM);
1036
1037         error = netdev_recv(port->netdev, &packet);
1038         if (!error) {
1039             dp_netdev_port_input(dp, port, &packet);
1040         } else if (error != EAGAIN && error != EOPNOTSUPP) {
1041             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
1042             VLOG_ERR_RL(&rl, "error receiving data from %s: %s",
1043                         netdev_get_name(port->netdev), strerror(error));
1044         }
1045     }
1046     ofpbuf_uninit(&packet);
1047 }
1048
1049 static void
1050 dpif_netdev_wait(struct dpif *dpif)
1051 {
1052     struct dp_netdev *dp = get_dp_netdev(dpif);
1053     struct dp_netdev_port *port;
1054
1055     LIST_FOR_EACH (port, node, &dp->port_list) {
1056         netdev_recv_wait(port->netdev);
1057     }
1058 }
1059
1060 static void
1061 dp_netdev_pop_vlan(struct ofpbuf *packet)
1062 {
1063     struct vlan_eth_header *veh = packet->l2;
1064     if (packet->size >= sizeof *veh
1065         && veh->veth_type == htons(ETH_TYPE_VLAN)) {
1066         struct eth_header tmp;
1067
1068         memcpy(tmp.eth_dst, veh->veth_dst, ETH_ADDR_LEN);
1069         memcpy(tmp.eth_src, veh->veth_src, ETH_ADDR_LEN);
1070         tmp.eth_type = veh->veth_next_type;
1071
1072         ofpbuf_pull(packet, VLAN_HEADER_LEN);
1073         packet->l2 = (char*)packet->l2 + VLAN_HEADER_LEN;
1074         memcpy(packet->data, &tmp, sizeof tmp);
1075     }
1076 }
1077
1078 static void
1079 dp_netdev_set_dl_src(struct ofpbuf *packet, const uint8_t dl_addr[ETH_ADDR_LEN])
1080 {
1081     struct eth_header *eh = packet->l2;
1082     memcpy(eh->eth_src, dl_addr, sizeof eh->eth_src);
1083 }
1084
1085 static void
1086 dp_netdev_set_dl_dst(struct ofpbuf *packet, const uint8_t dl_addr[ETH_ADDR_LEN])
1087 {
1088     struct eth_header *eh = packet->l2;
1089     memcpy(eh->eth_dst, dl_addr, sizeof eh->eth_dst);
1090 }
1091
1092 static bool
1093 is_ip(const struct ofpbuf *packet, const struct flow *key)
1094 {
1095     return key->dl_type == htons(ETH_TYPE_IP) && packet->l4;
1096 }
1097
1098 static void
1099 dp_netdev_set_nw_addr(struct ofpbuf *packet, const struct flow *key,
1100                       const struct nlattr *a)
1101 {
1102     if (is_ip(packet, key)) {
1103         struct ip_header *nh = packet->l3;
1104         ovs_be32 ip = nl_attr_get_be32(a);
1105         uint16_t type = nl_attr_type(a);
1106         ovs_be32 *field;
1107
1108         field = type == OVS_ACTION_ATTR_SET_NW_SRC ? &nh->ip_src : &nh->ip_dst;
1109         if (key->nw_proto == IPPROTO_TCP && packet->l7) {
1110             struct tcp_header *th = packet->l4;
1111             th->tcp_csum = recalc_csum32(th->tcp_csum, *field, ip);
1112         } else if (key->nw_proto == IPPROTO_UDP && packet->l7) {
1113             struct udp_header *uh = packet->l4;
1114             if (uh->udp_csum) {
1115                 uh->udp_csum = recalc_csum32(uh->udp_csum, *field, ip);
1116                 if (!uh->udp_csum) {
1117                     uh->udp_csum = htons(0xffff);
1118                 }
1119             }
1120         }
1121         nh->ip_csum = recalc_csum32(nh->ip_csum, *field, ip);
1122         *field = ip;
1123     }
1124 }
1125
1126 static void
1127 dp_netdev_set_nw_tos(struct ofpbuf *packet, const struct flow *key,
1128                      uint8_t nw_tos)
1129 {
1130     if (is_ip(packet, key)) {
1131         struct ip_header *nh = packet->l3;
1132         uint8_t *field = &nh->ip_tos;
1133
1134         /* Set the DSCP bits and preserve the ECN bits. */
1135         uint8_t new = nw_tos | (nh->ip_tos & IP_ECN_MASK);
1136
1137         nh->ip_csum = recalc_csum16(nh->ip_csum, htons((uint16_t)*field),
1138                 htons((uint16_t) new));
1139         *field = new;
1140     }
1141 }
1142
1143 static void
1144 dp_netdev_set_tp_port(struct ofpbuf *packet, const struct flow *key,
1145                       const struct nlattr *a)
1146 {
1147         if (is_ip(packet, key)) {
1148         uint16_t type = nl_attr_type(a);
1149         ovs_be16 port = nl_attr_get_be16(a);
1150         ovs_be16 *field;
1151
1152         if (key->nw_proto == IPPROTO_TCP && packet->l7) {
1153             struct tcp_header *th = packet->l4;
1154             field = (type == OVS_ACTION_ATTR_SET_TP_SRC
1155                      ? &th->tcp_src : &th->tcp_dst);
1156             th->tcp_csum = recalc_csum16(th->tcp_csum, *field, port);
1157             *field = port;
1158         } else if (key->nw_proto == IPPROTO_UDP && packet->l7) {
1159             struct udp_header *uh = packet->l4;
1160             field = (type == OVS_ACTION_ATTR_SET_TP_SRC
1161                      ? &uh->udp_src : &uh->udp_dst);
1162             uh->udp_csum = recalc_csum16(uh->udp_csum, *field, port);
1163             *field = port;
1164         } else {
1165             return;
1166         }
1167     }
1168 }
1169
1170 static void
1171 dp_netdev_output_port(struct dp_netdev *dp, struct ofpbuf *packet,
1172                       uint16_t out_port)
1173 {
1174     struct dp_netdev_port *p = dp->ports[out_port];
1175     if (p) {
1176         netdev_send(p->netdev, packet);
1177     }
1178 }
1179
1180 static int
1181 dp_netdev_output_userspace(struct dp_netdev *dp, const struct ofpbuf *packet,
1182                          int queue_no, const struct flow *flow, uint64_t arg)
1183 {
1184     struct dp_netdev_queue *q = &dp->queues[queue_no];
1185     struct dpif_upcall *upcall;
1186     struct ofpbuf *buf;
1187     size_t key_len;
1188
1189     if (q->head - q->tail >= MAX_QUEUE_LEN) {
1190         dp->n_lost++;
1191         return ENOBUFS;
1192     }
1193
1194     buf = ofpbuf_new(ODPUTIL_FLOW_KEY_BYTES + 2 + packet->size);
1195     odp_flow_key_from_flow(buf, flow);
1196     key_len = buf->size;
1197     ofpbuf_pull(buf, key_len);
1198     ofpbuf_reserve(buf, 2);
1199     ofpbuf_put(buf, packet->data, packet->size);
1200
1201     upcall = xzalloc(sizeof *upcall);
1202     upcall->type = queue_no;
1203     upcall->packet = buf;
1204     upcall->key = buf->base;
1205     upcall->key_len = key_len;
1206     upcall->userdata = arg;
1207
1208     q->upcalls[q->head++ & QUEUE_MASK] = upcall;
1209
1210     return 0;
1211 }
1212
1213 static void
1214 dp_netdev_sample(struct dp_netdev *dp,
1215                  struct ofpbuf *packet, struct flow *key,
1216                  const struct nlattr *action)
1217 {
1218     const struct nlattr *subactions = NULL;
1219     const struct nlattr *a;
1220     size_t left;
1221
1222     NL_NESTED_FOR_EACH_UNSAFE (a, left, action) {
1223         int type = nl_attr_type(a);
1224
1225         switch ((enum ovs_sample_attr) type) {
1226         case OVS_SAMPLE_ATTR_PROBABILITY:
1227             if (random_uint32() >= nl_attr_get_u32(a)) {
1228                 return;
1229             }
1230             break;
1231
1232         case OVS_SAMPLE_ATTR_ACTIONS:
1233             subactions = a;
1234             break;
1235
1236         case OVS_SAMPLE_ATTR_UNSPEC:
1237         case __OVS_SAMPLE_ATTR_MAX:
1238         default:
1239             NOT_REACHED();
1240         }
1241     }
1242
1243     dp_netdev_execute_actions(dp, packet, key, nl_attr_get(subactions),
1244                               nl_attr_get_size(subactions));
1245 }
1246
1247 static void
1248 dp_netdev_action_userspace(struct dp_netdev *dp,
1249                           struct ofpbuf *packet, struct flow *key,
1250                           const struct nlattr *a)
1251 {
1252     const struct nlattr *userdata_attr;
1253     uint64_t userdata;
1254
1255     userdata_attr = nl_attr_find_nested(a, OVS_USERSPACE_ATTR_USERDATA);
1256     userdata = userdata_attr ? nl_attr_get_u64(userdata_attr) : 0;
1257     dp_netdev_output_userspace(dp, packet, DPIF_UC_ACTION, key, userdata);
1258 }
1259
1260 static int
1261 dp_netdev_execute_actions(struct dp_netdev *dp,
1262                           struct ofpbuf *packet, struct flow *key,
1263                           const struct nlattr *actions,
1264                           size_t actions_len)
1265 {
1266     const struct nlattr *a;
1267     unsigned int left;
1268
1269     NL_ATTR_FOR_EACH_UNSAFE (a, left, actions, actions_len) {
1270         int type = nl_attr_type(a);
1271
1272         switch ((enum ovs_action_type) type) {
1273         case OVS_ACTION_ATTR_OUTPUT:
1274             dp_netdev_output_port(dp, packet, nl_attr_get_u32(a));
1275             break;
1276
1277         case OVS_ACTION_ATTR_USERSPACE:
1278             dp_netdev_action_userspace(dp, packet, key, a);
1279             break;
1280
1281         case OVS_ACTION_ATTR_PUSH_VLAN:
1282             eth_push_vlan(packet, nl_attr_get_be16(a));
1283             break;
1284
1285         case OVS_ACTION_ATTR_POP_VLAN:
1286             dp_netdev_pop_vlan(packet);
1287             break;
1288
1289         case OVS_ACTION_ATTR_SET_DL_SRC:
1290             dp_netdev_set_dl_src(packet, nl_attr_get_unspec(a, ETH_ADDR_LEN));
1291             break;
1292
1293         case OVS_ACTION_ATTR_SET_DL_DST:
1294             dp_netdev_set_dl_dst(packet, nl_attr_get_unspec(a, ETH_ADDR_LEN));
1295             break;
1296
1297         case OVS_ACTION_ATTR_SET_NW_SRC:
1298         case OVS_ACTION_ATTR_SET_NW_DST:
1299             dp_netdev_set_nw_addr(packet, key, a);
1300             break;
1301
1302         case OVS_ACTION_ATTR_SET_NW_TOS:
1303             dp_netdev_set_nw_tos(packet, key, nl_attr_get_u8(a));
1304             break;
1305
1306         case OVS_ACTION_ATTR_SET_TP_SRC:
1307         case OVS_ACTION_ATTR_SET_TP_DST:
1308             dp_netdev_set_tp_port(packet, key, a);
1309             break;
1310
1311         case OVS_ACTION_ATTR_SAMPLE:
1312             dp_netdev_sample(dp, packet, key, a);
1313             break;
1314
1315         case OVS_ACTION_ATTR_SET_TUNNEL:
1316         case OVS_ACTION_ATTR_SET_PRIORITY:
1317         case OVS_ACTION_ATTR_POP_PRIORITY:
1318             /* not implemented */
1319             break;
1320
1321         case OVS_ACTION_ATTR_UNSPEC:
1322         case __OVS_ACTION_ATTR_MAX:
1323             NOT_REACHED();
1324         }
1325     }
1326     return 0;
1327 }
1328
1329 const struct dpif_class dpif_netdev_class = {
1330     "netdev",
1331     NULL,                       /* enumerate */
1332     dpif_netdev_open,
1333     dpif_netdev_close,
1334     dpif_netdev_destroy,
1335     dpif_netdev_run,
1336     dpif_netdev_wait,
1337     dpif_netdev_get_stats,
1338     dpif_netdev_get_drop_frags,
1339     dpif_netdev_set_drop_frags,
1340     dpif_netdev_port_add,
1341     dpif_netdev_port_del,
1342     dpif_netdev_port_query_by_number,
1343     dpif_netdev_port_query_by_name,
1344     dpif_netdev_get_max_ports,
1345     NULL,                       /* port_get_pid */
1346     dpif_netdev_port_dump_start,
1347     dpif_netdev_port_dump_next,
1348     dpif_netdev_port_dump_done,
1349     dpif_netdev_port_poll,
1350     dpif_netdev_port_poll_wait,
1351     dpif_netdev_flow_get,
1352     dpif_netdev_flow_put,
1353     dpif_netdev_flow_del,
1354     dpif_netdev_flow_flush,
1355     dpif_netdev_flow_dump_start,
1356     dpif_netdev_flow_dump_next,
1357     dpif_netdev_flow_dump_done,
1358     dpif_netdev_execute,
1359     dpif_netdev_recv_get_mask,
1360     dpif_netdev_recv_set_mask,
1361     NULL,                       /* queue_to_priority */
1362     dpif_netdev_recv,
1363     dpif_netdev_recv_wait,
1364     dpif_netdev_recv_purge,
1365 };
1366
1367 void
1368 dpif_dummy_register(void)
1369 {
1370     if (!dpif_dummy_class.type) {
1371         dpif_dummy_class = dpif_netdev_class;
1372         dpif_dummy_class.type = "dummy";
1373         dp_register_provider(&dpif_dummy_class);
1374     }
1375 }