pintos-os.org Git - openvswitch/blob - switch/forward.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   4  * We are making the OpenFlow specification and associated documentation
   5  * (Software) available for public use and benefit with the expectation
   6  * that others will use, modify and enhance the Software and contribute
   7  * those enhancements back to the community. However, since we would
   8  * like to make the Software available for broadest use, with as few
   9  * restrictions as possible permission is hereby granted, free of
  10  * charge, to any person obtaining a copy of this Software to deal in
  11  * the Software under the copyrights without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * The name and trademarks of copyright holder(s) may NOT be used in
  30  * advertising or publicity pertaining to the Software or any
  31  * derivatives without specific, written prior permission.
  32  */
  33
  34 #include "forward.h"
  35 #include <arpa/inet.h>
  36 #include <assert.h>
  37 #include <errno.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include "datapath.h"
  41 #include "chain.h"
  42 #include "flow.h"
  43 #include "packets.h"
  44
  45 static void execute_actions(struct datapath *, struct buffer *,
  46                             int in_port, const struct sw_flow_key *,
  47                             const struct ofp_action *, int n_actions);
  48
  49 static struct buffer *retrieve_buffer(uint32_t id);
  50 static void discard_buffer(uint32_t id);
  51
  52 /* 'buffer' was received on 'in_port', a physical switch port between 0 and
  53  * OFPP_MAX.  Process it according to 'chain'. */
  54 void fwd_port_input(struct datapath *dp, struct buffer *buffer, int in_port)
  55 {
  56     struct sw_flow_key key;
  57     struct sw_flow *flow;
  58
  59     key.wildcards = 0;
  60     flow_extract(buffer, in_port, &key.flow);
  61     flow = chain_lookup(dp->chain, &key);
  62     if (flow != NULL) {
  63         flow_used(flow, buffer);
  64         execute_actions(dp, buffer, in_port, &key,
  65                         flow->actions, flow->n_actions);
  66     } else {
  67         dp_output_control(dp, buffer, in_port, fwd_save_buffer(buffer),
  68                           dp->miss_send_len, OFPR_NO_MATCH);
  69     }
  70 }
  71
  72 static void
  73 do_output(struct datapath *dp, struct buffer *buffer, int in_port,
  74           size_t max_len, int out_port)
  75 {
  76     if (out_port != OFPP_CONTROLLER) {
  77         dp_output_port(dp, buffer, in_port, out_port);
  78     } else {
  79         dp_output_control(dp, buffer, in_port, fwd_save_buffer(buffer),
  80                           max_len, OFPR_ACTION);
  81     }
  82 }
  83
  84 static void execute_actions(struct datapath *dp, struct buffer *buffer,
  85                             int in_port, const struct sw_flow_key *key,
  86                             const struct ofp_action *actions, int n_actions)
  87 {
  88     /* Every output action needs a separate clone of 'buffer', but the common
  89      * case is just a single output action, so that doing a clone and then
  90      * freeing the original buffer is wasteful.  So the following code is
  91      * slightly obscure just to avoid that. */
  92     int prev_port;
  93     size_t max_len=0;        /* Initialze to make compiler happy */
  94     uint16_t eth_proto;
  95     int i;
  96
  97     prev_port = -1;
  98     eth_proto = ntohs(key->flow.dl_type);
  99
 100     for (i = 0; i < n_actions; i++) {
 101         const struct ofp_action *a = &actions[i];
 102
 103         if (prev_port != -1) {
 104             do_output(dp, buffer_clone(buffer), in_port, max_len, prev_port);
 105             prev_port = -1;
 106         }
 107
 108         if (a->type == ntohs(OFPAT_OUTPUT)) {
 109             prev_port = ntohs(a->arg.output.port);
 110             max_len = ntohs(a->arg.output.max_len);
 111         } else {
 112             buffer = execute_setter(buffer, eth_proto, key, a);
 113         }
 114     }
 115     if (prev_port != -1)
 116         do_output(dp, buffer, in_port, max_len, prev_port);
 117     else
 118         buffer_delete(buffer);
 119 }
 120
 121 /* Returns the new checksum for a packet in which the checksum field previously
 122  * contained 'old_csum' and in which a field that contained 'old_u16' was
 123  * changed to contain 'new_u16'. */
 124 static uint16_t
 125 recalc_csum16(uint16_t old_csum, uint16_t old_u16, uint16_t new_u16)
 126 {
 127     /* Ones-complement arithmetic is endian-independent, so this code does not
 128      * use htons() or ntohs().
 129      *
 130      * See RFC 1624 for formula and explanation. */
 131     uint16_t hc_complement = ~old_csum;
 132     uint16_t m_complement = ~old_u16;
 133     uint16_t m_prime = new_u16;
 134     uint32_t sum = hc_complement + m_complement + m_prime;
 135     uint16_t hc_prime_complement = sum + (sum >> 16);
 136     return ~hc_prime_complement;
 137 }
 138
 139 /* Returns the new checksum for a packet in which the checksum field previously
 140  * contained 'old_csum' and in which a field that contained 'old_u32' was
 141  * changed to contain 'new_u32'. */
 142 static uint16_t
 143 recalc_csum32(uint16_t old_csum, uint32_t old_u32, uint32_t new_u32)
 144 {
 145     return recalc_csum16(recalc_csum16(old_csum, old_u32, new_u32),
 146                          old_u32 >> 16, new_u32 >> 16);
 147 }
 148
 149 static void modify_nh(struct buffer *buffer, uint16_t eth_proto,
 150                       uint8_t nw_proto, const struct ofp_action *a)
 151 {
 152     if (eth_proto == ETH_TYPE_IP) {
 153         struct ip_header *nh = buffer->l3;
 154         uint32_t new, *field;
 155
 156         new = a->arg.nw_addr;
 157         field = a->type == OFPAT_SET_NW_SRC ? &nh->ip_src : &nh->ip_dst;
 158         if (nw_proto == IP_TYPE_TCP) {
 159             struct tcp_header *th = buffer->l4;
 160             th->tcp_csum = recalc_csum32(th->tcp_csum, *field, new);
 161         } else if (nw_proto == IP_TYPE_UDP) {
 162             struct udp_header *th = buffer->l4;
 163             if (th->udp_csum) {
 164                 th->udp_csum = recalc_csum32(th->udp_csum, *field, new);
 165                 if (!th->udp_csum) {
 166                     th->udp_csum = 0xffff;
 167                 }
 168             }
 169         }
 170         nh->ip_csum = recalc_csum32(nh->ip_csum, *field, new);
 171         *field = new;
 172     }
 173 }
 174
 175 static void modify_th(struct buffer *buffer, uint16_t eth_proto,
 176                       uint8_t nw_proto, const struct ofp_action *a)
 177 {
 178     if (eth_proto == ETH_TYPE_IP) {
 179         uint16_t new, *field;
 180
 181         new = a->arg.tp;
 182
 183         if (nw_proto == IP_TYPE_TCP) {
 184             struct tcp_header *th = buffer->l4;
 185             field = a->type == OFPAT_SET_TP_SRC ? &th->tcp_src : &th->tcp_dst;
 186             th->tcp_csum = recalc_csum16(th->tcp_csum, *field, new);
 187             *field = new;
 188         } else if (nw_proto == IP_TYPE_UDP) {
 189             struct udp_header *th = buffer->l4;
 190             field = a->type == OFPAT_SET_TP_SRC ? &th->udp_src : &th->udp_dst;
 191             th->udp_csum = recalc_csum16(th->udp_csum, *field, new);
 192             *field = new;
 193         }
 194     }
 195 }
 196
 197 static struct buffer *
 198 modify_vlan(struct buffer *buffer,
 199             const struct sw_flow_key *key, const struct ofp_action *a)
 200 {
 201     uint16_t new_id = a->arg.vlan_id;
 202     struct vlan_eth_header *veh;
 203
 204     if (new_id != OFP_VLAN_NONE) {
 205         if (key->flow.dl_vlan != htons(OFP_VLAN_NONE)) {
 206             /* Modify vlan id, but maintain other TCI values */
 207             veh = buffer->l2;
 208             veh->veth_tci &= ~htons(VLAN_VID);
 209             veh->veth_tci |= htons(new_id);
 210         } else {
 211             /* Insert new vlan id. */
 212             struct eth_header *eh = buffer->l2;
 213             struct vlan_eth_header tmp;
 214             memcpy(tmp.veth_dst, eh->eth_dst, ETH_ADDR_LEN);
 215             memcpy(tmp.veth_src, eh->eth_src, ETH_ADDR_LEN);
 216             tmp.veth_type = htons(ETH_TYPE_VLAN);
 217             tmp.veth_tci = new_id;
 218             tmp.veth_next_type = eh->eth_type;
 219
 220             veh = buffer_push_uninit(buffer, VLAN_HEADER_LEN);
 221             memcpy(veh, &tmp, sizeof tmp);
 222             buffer->l2 -= VLAN_HEADER_LEN;
 223         }
 224     } else  {
 225         /* Remove an existing vlan header if it exists */
 226         veh = buffer->l2;
 227         if (veh->veth_type == htons(ETH_TYPE_VLAN)) {
 228             struct eth_header tmp;
 229
 230             memcpy(tmp.eth_dst, veh->veth_dst, ETH_ADDR_LEN);
 231             memcpy(tmp.eth_src, veh->veth_src, ETH_ADDR_LEN);
 232             tmp.eth_type = veh->veth_next_type;
 233
 234             buffer->size -= VLAN_HEADER_LEN;
 235             buffer->data += VLAN_HEADER_LEN;
 236             buffer->l2 += VLAN_HEADER_LEN;
 237             memcpy(buffer->data, &tmp, sizeof tmp);
 238         }
 239     }
 240
 241     return buffer;
 242 }
 243
 244 struct buffer *execute_setter(struct buffer *buffer, uint16_t eth_proto,
 245                               const struct sw_flow_key *key, const struct ofp_action *a)
 246 {
 247     switch (a->type) {
 248     case OFPAT_SET_DL_VLAN:
 249         buffer = modify_vlan(buffer, key, a);
 250         break;
 251
 252     case OFPAT_SET_DL_SRC: {
 253         struct eth_header *eh = buffer->l2;
 254         memcpy(eh->eth_src, a->arg.dl_addr, sizeof eh->eth_src);
 255         break;
 256     }
 257     case OFPAT_SET_DL_DST: {
 258         struct eth_header *eh = buffer->l2;
 259         memcpy(eh->eth_dst, a->arg.dl_addr, sizeof eh->eth_dst);
 260         break;
 261     }
 262
 263     case OFPAT_SET_NW_SRC:
 264     case OFPAT_SET_NW_DST:
 265         modify_nh(buffer, eth_proto, key->flow.nw_proto, a);
 266         break;
 267
 268     case OFPAT_SET_TP_SRC:
 269     case OFPAT_SET_TP_DST:
 270         modify_th(buffer, eth_proto, key->flow.nw_proto, a);
 271         break;
 272
 273     default:
 274         NOT_REACHED();
 275     }
 276
 277     return buffer;
 278 }
 279
 280 static int
 281 recv_control_hello(struct datapath *dp, const void *msg)
 282 {
 283     const struct ofp_control_hello *och = msg;
 284
 285     printf("control_hello(version=%d)\n", ntohl(och->version));
 286
 287     if (ntohs(och->miss_send_len) != OFP_MISS_SEND_LEN_UNCHANGED) {
 288         dp->miss_send_len = ntohs(och->miss_send_len);
 289     }
 290
 291     dp->hello_flags = ntohs(och->flags);
 292
 293     dp_send_hello(dp);
 294
 295     return 0;
 296 }
 297
 298 static int
 299 recv_packet_out(struct datapath *dp, const void *msg)
 300 {
 301     const struct ofp_packet_out *opo = msg;
 302
 303     if (ntohl(opo->buffer_id) == (uint32_t) -1) {
 304         /* FIXME: can we avoid copying data here? */
 305         int data_len = ntohs(opo->header.length) - sizeof *opo;
 306         struct buffer *buffer = buffer_new(data_len);
 307         buffer_put(buffer, opo->u.data, data_len);
 308         dp_output_port(dp, buffer,
 309                        ntohs(opo->in_port), ntohs(opo->out_port));
 310     } else {
 311         struct sw_flow_key key;
 312         struct buffer *buffer;
 313         int n_acts;
 314
 315         buffer = retrieve_buffer(ntohl(opo->buffer_id));
 316         if (!buffer) {
 317             return -ESRCH;
 318         }
 319
 320         n_acts = (ntohs(opo->header.length) - sizeof *opo)
 321             / sizeof *opo->u.actions;
 322         flow_extract(buffer, ntohs(opo->in_port), &key.flow);
 323         execute_actions(dp, buffer, ntohs(opo->in_port),
 324                         &key, opo->u.actions, n_acts);
 325     }
 326     return 0;
 327 }
 328
 329 static int
 330 recv_port_mod(struct datapath *dp, const void *msg)
 331 {
 332     const struct ofp_port_mod *opm = msg;
 333
 334     dp_update_port_flags(dp, &opm->desc);
 335
 336     return 0;
 337 }
 338
 339 static int
 340 add_flow(struct datapath *dp, const struct ofp_flow_mod *ofm)
 341 {
 342     int error = -ENOMEM;
 343     int n_acts;
 344     struct sw_flow *flow;
 345
 346
 347     /* Check number of actions. */
 348     n_acts = (ntohs(ofm->header.length) - sizeof *ofm) / sizeof *ofm->actions;
 349     if (n_acts > MAX_ACTIONS) {
 350         error = -E2BIG;
 351         goto error;
 352     }
 353
 354     /* Allocate memory. */
 355     flow = flow_alloc(n_acts);
 356     if (flow == NULL)
 357         goto error;
 358
 359     /* Fill out flow. */
 360     flow_extract_match(&flow->key, &ofm->match);
 361     flow->group_id = ntohl(ofm->group_id);
 362     flow->max_idle = ntohs(ofm->max_idle);
 363     flow->timeout = time(0) + flow->max_idle; /* FIXME */
 364     flow->n_actions = n_acts;
 365     flow->created = time(0);    /* FIXME */
 366     flow->byte_count = 0;
 367     flow->packet_count = 0;
 368     memcpy(flow->actions, ofm->actions, n_acts * sizeof *flow->actions);
 369
 370     /* Act. */
 371     error = chain_insert(dp->chain, flow);
 372     if (error) {
 373         goto error_free_flow;
 374     }
 375     error = 0;
 376     if (ntohl(ofm->buffer_id) != UINT32_MAX) {
 377         struct buffer *buffer = retrieve_buffer(ntohl(ofm->buffer_id));
 378         if (buffer) {
 379             struct sw_flow_key key;
 380             uint16_t in_port = ntohs(ofm->match.in_port);
 381             flow_used(flow, buffer);
 382             flow_extract(buffer, in_port, &key.flow);
 383             execute_actions(dp, buffer, in_port,
 384                             &key, ofm->actions, n_acts);
 385         } else {
 386             error = -ESRCH;
 387         }
 388     }
 389     return error;
 390
 391 error_free_flow:
 392     flow_free(flow);
 393 error:
 394     if (ntohl(ofm->buffer_id) != (uint32_t) -1)
 395         discard_buffer(ntohl(ofm->buffer_id));
 396     return error;
 397 }
 398
 399 static int
 400 recv_flow(struct datapath *dp, const void *msg)
 401 {
 402     const struct ofp_flow_mod *ofm = msg;
 403     uint16_t command = ntohs(ofm->command);
 404
 405     if (command == OFPFC_ADD) {
 406         return add_flow(dp, ofm);
 407     }  else if (command == OFPFC_DELETE) {
 408         struct sw_flow_key key;
 409         flow_extract_match(&key, &ofm->match);
 410         return chain_delete(dp->chain, &key, 0) ? 0 : -ESRCH;
 411     } else if (command == OFPFC_DELETE_STRICT) {
 412         struct sw_flow_key key;
 413         flow_extract_match(&key, &ofm->match);
 414         return chain_delete(dp->chain, &key, 1) ? 0 : -ESRCH;
 415     } else {
 416         return -ENODEV;
 417     }
 418 }
 419
 420 /* 'msg', which is 'length' bytes long, was received from the control path.
 421  * Apply it to 'chain'. */
 422 int
 423 fwd_control_input(struct datapath *dp, const void *msg, size_t length)
 424 {
 425
 426     struct openflow_packet {
 427         size_t min_size;
 428         int (*handler)(struct datapath *, const void *);
 429     };
 430
 431     static const struct openflow_packet packets[] = {
 432         [OFPT_CONTROL_HELLO] = {
 433             sizeof (struct ofp_control_hello),
 434             recv_control_hello,
 435         },
 436         [OFPT_PACKET_OUT] = {
 437             sizeof (struct ofp_packet_out),
 438             recv_packet_out,
 439         },
 440         [OFPT_FLOW_MOD] = {
 441             sizeof (struct ofp_flow_mod),
 442             recv_flow,
 443         },
 444         [OFPT_PORT_MOD] = {
 445             sizeof (struct ofp_port_mod),
 446             recv_port_mod,
 447         },
 448     };
 449
 450     const struct openflow_packet *pkt;
 451     struct ofp_header *oh;
 452
 453     if (length < sizeof(struct ofp_header))
 454         return -EINVAL;
 455
 456     oh = (struct ofp_header *) msg;
 457     if (oh->version != 1 || oh->type >= ARRAY_SIZE(packets)
 458         || ntohs(oh->length) > length)
 459         return -EINVAL;
 460
 461     pkt = &packets[oh->type];
 462     if (!pkt->handler)
 463         return -ENOSYS;
 464     if (length < pkt->min_size)
 465         return -EFAULT;
 466
 467     return pkt->handler(dp, msg);
 468 }
 469
 470 /* Packet buffering. */
 471
 472 #define OVERWRITE_SECS  1
 473
 474 struct packet_buffer {
 475     struct buffer *buffer;
 476     uint32_t cookie;
 477     time_t timeout;
 478 };
 479
 480 static struct packet_buffer buffers[N_PKT_BUFFERS];
 481 static unsigned int buffer_idx;
 482
 483 uint32_t fwd_save_buffer(struct buffer *buffer)
 484 {
 485     struct packet_buffer *p;
 486     uint32_t id;
 487
 488     buffer_idx = (buffer_idx + 1) & PKT_BUFFER_MASK;
 489     p = &buffers[buffer_idx];
 490     if (p->buffer) {
 491         /* Don't buffer packet if existing entry is less than
 492          * OVERWRITE_SECS old. */
 493         if (time(0) < p->timeout) { /* FIXME */
 494             return -1;
 495         } else {
 496             buffer_delete(p->buffer);
 497         }
 498     }
 499     /* Don't use maximum cookie value since the all-bits-1 id is
 500      * special. */
 501     if (++p->cookie >= (1u << PKT_COOKIE_BITS) - 1)
 502         p->cookie = 0;
 503     p->buffer = buffer_clone(buffer);      /* FIXME */
 504     p->timeout = time(0) + OVERWRITE_SECS; /* FIXME */
 505     id = buffer_idx | (p->cookie << PKT_BUFFER_BITS);
 506
 507     return id;
 508 }
 509
 510 static struct buffer *retrieve_buffer(uint32_t id)
 511 {
 512     struct buffer *buffer = NULL;
 513     struct packet_buffer *p;
 514
 515     p = &buffers[id & PKT_BUFFER_MASK];
 516     if (p->cookie == id >> PKT_BUFFER_BITS) {
 517         buffer = p->buffer;
 518         p->buffer = NULL;
 519     } else {
 520         printf("cookie mismatch: %x != %x\n",
 521                id >> PKT_BUFFER_BITS, p->cookie);
 522     }
 523
 524     return buffer;
 525 }
 526
 527 static void discard_buffer(uint32_t id)
 528 {
 529     struct packet_buffer *p;
 530
 531     p = &buffers[id & PKT_BUFFER_MASK];
 532     if (p->cookie == id >> PKT_BUFFER_BITS) {
 533         buffer_delete(p->buffer);
 534         p->buffer = NULL;
 535     }
 536 }
 537
 538 void fwd_exit(void)
 539 {
 540     int i;
 541
 542     for (i = 0; i < N_PKT_BUFFERS; i++)
 543         buffer_delete(buffers[i].buffer);
 544 }