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

   1 /*
   2  * Distributed under the terms of the GNU GPL version 2.
   3  * Copyright (c) 2007, 2008 The Board of Trustees of The Leland
   4  * Stanford Junior University
   5  */
   6
   7 #include <linux/if_ether.h>
   8 #include <linux/if_vlan.h>
   9 #include <linux/in.h>
  10 #include <linux/ip.h>
  11 #include <linux/tcp.h>
  12 #include <linux/udp.h>
  13 #include <linux/in6.h>
  14 #include <asm/uaccess.h>
  15 #include <linux/types.h>
  16 #include <net/checksum.h>
  17 #include "forward.h"
  18 #include "datapath.h"
  19 #include "chain.h"
  20 #include "flow.h"
  21
  22 /* FIXME: do we need to use GFP_ATOMIC everywhere here? */
  23
  24 static void execute_actions(struct datapath *, struct sk_buff *,
  25                                 const struct sw_flow_key *,
  26                                 const struct ofp_action *, int n_actions);
  27 static int make_writable(struct sk_buff **);
  28
  29 static struct sk_buff *retrieve_skb(uint32_t id);
  30 static void discard_skb(uint32_t id);
  31
  32 /* 'skb' was received on 'in_port', a physical switch port between 0 and
  33  * OFPP_MAX.  Process it according to 'chain'. */
  34 void fwd_port_input(struct sw_chain *chain, struct sk_buff *skb, int in_port)
  35 {
  36         struct sw_flow_key key;
  37         struct sw_flow *flow;
  38
  39         flow_extract(skb, in_port, &key);
  40         flow = chain_lookup(chain, &key);
  41         if (likely(flow != NULL)) {
  42                 flow_used(flow, skb);
  43                 execute_actions(chain->dp, skb, &key,
  44                                 flow->actions, flow->n_actions);
  45         } else {
  46                 dp_output_control(chain->dp, skb, fwd_save_skb(skb),
  47                                   chain->dp->config.miss_send_len,
  48                                   OFPR_NO_MATCH);
  49         }
  50 }
  51
  52 static int do_output(struct datapath *dp, struct sk_buff *skb, size_t max_len,
  53                         int out_port)
  54 {
  55         if (!skb)
  56                 return -ENOMEM;
  57         return (likely(out_port != OFPP_CONTROLLER)
  58                 ? dp_output_port(dp, skb, out_port)
  59                 : dp_output_control(dp, skb, fwd_save_skb(skb),
  60                                          max_len, OFPR_ACTION));
  61 }
  62
  63 static void execute_actions(struct datapath *dp, struct sk_buff *skb,
  64                                 const struct sw_flow_key *key,
  65                                 const struct ofp_action *actions, int n_actions)
  66 {
  67         /* Every output action needs a separate clone of 'skb', but the common
  68          * case is just a single output action, so that doing a clone and
  69          * then freeing the original skbuff is wasteful.  So the following code
  70          * is slightly obscure just to avoid that. */
  71         int prev_port;
  72         size_t max_len=0;        /* Initialze to make compiler happy */
  73         uint16_t eth_proto;
  74         int i;
  75
  76         prev_port = -1;
  77         eth_proto = ntohs(key->dl_type);
  78
  79         for (i = 0; i < n_actions; i++) {
  80                 const struct ofp_action *a = &actions[i];
  81
  82                 if (prev_port != -1) {
  83                         do_output(dp, skb_clone(skb, GFP_ATOMIC),
  84                                   max_len, prev_port);
  85                         prev_port = -1;
  86                 }
  87
  88                 if (likely(a->type == htons(OFPAT_OUTPUT))) {
  89                         prev_port = ntohs(a->arg.output.port);
  90                         max_len = ntohs(a->arg.output.max_len);
  91                 } else {
  92                         if (!make_writable(&skb)) {
  93                                 printk("make_writable failed\n");
  94                                 break;
  95                         }
  96                         skb = execute_setter(skb, eth_proto, key, a);
  97                 }
  98         }
  99         if (prev_port != -1)
 100                 do_output(dp, skb, max_len, prev_port);
 101         else
 102                 kfree_skb(skb);
 103 }
 104
 105 /* Updates 'sum', which is a field in 'skb''s data, given that a 4-byte field
 106  * covered by the sum has been changed from 'from' to 'to'.  If set,
 107  * 'pseudohdr' indicates that the field is in the TCP or UDP pseudo-header.
 108  * Based on nf_proto_csum_replace4. */
 109 static void update_csum(__sum16 *sum, struct sk_buff *skb,
 110                         __be32 from, __be32 to, int pseudohdr)
 111 {
 112         __be32 diff[] = { ~from, to };
 113         if (skb->ip_summed != CHECKSUM_PARTIAL) {
 114                 *sum = csum_fold(csum_partial((char *)diff, sizeof(diff),
 115                                 ~csum_unfold(*sum)));
 116                 if (skb->ip_summed == CHECKSUM_COMPLETE && pseudohdr)
 117                         skb->csum = ~csum_partial((char *)diff, sizeof(diff),
 118                                                 ~skb->csum);
 119         } else if (pseudohdr)
 120                 *sum = ~csum_fold(csum_partial((char *)diff, sizeof(diff),
 121                                 csum_unfold(*sum)));
 122 }
 123
 124 static void modify_nh(struct sk_buff *skb, uint16_t eth_proto,
 125                         uint8_t nw_proto, const struct ofp_action *a)
 126 {
 127         if (eth_proto == ETH_P_IP) {
 128                 struct iphdr *nh = ip_hdr(skb);
 129                 uint32_t new, *field;
 130
 131                 new = a->arg.nw_addr;
 132
 133                 if (a->type == htons(OFPAT_SET_NW_SRC))
 134                         field = &nh->saddr;
 135                 else
 136                         field = &nh->daddr;
 137
 138                 if (nw_proto == IPPROTO_TCP) {
 139                         struct tcphdr *th = tcp_hdr(skb);
 140                         update_csum(&th->check, skb, *field, new, 1);
 141                 } else if (nw_proto == IPPROTO_UDP) {
 142                         struct udphdr *th = udp_hdr(skb);
 143                         update_csum(&th->check, skb, *field, new, 1);
 144                 }
 145                 update_csum(&nh->check, skb, *field, new, 0);
 146                 *field = new;
 147         }
 148 }
 149
 150 static void modify_th(struct sk_buff *skb, uint16_t eth_proto,
 151                         uint8_t nw_proto, const struct ofp_action *a)
 152 {
 153         if (eth_proto == ETH_P_IP) {
 154                 uint16_t new, *field;
 155
 156                 new = a->arg.tp;
 157
 158                 if (nw_proto == IPPROTO_TCP) {
 159                         struct tcphdr *th = tcp_hdr(skb);
 160
 161                         if (a->type == htons(OFPAT_SET_TP_SRC))
 162                                 field = &th->source;
 163                         else
 164                                 field = &th->dest;
 165
 166                         update_csum(&th->check, skb, *field, new, 1);
 167                         *field = new;
 168                 } else if (nw_proto == IPPROTO_UDP) {
 169                         struct udphdr *th = udp_hdr(skb);
 170
 171                         if (a->type == htons(OFPAT_SET_TP_SRC))
 172                                 field = &th->source;
 173                         else
 174                                 field = &th->dest;
 175
 176                         update_csum(&th->check, skb, *field, new, 1);
 177                         *field = new;
 178                 }
 179         }
 180 }
 181
 182 static struct sk_buff *vlan_pull_tag(struct sk_buff *skb)
 183 {
 184         struct vlan_ethhdr *vh = vlan_eth_hdr(skb);
 185         struct ethhdr *eh;
 186
 187
 188         /* Verify we were given a vlan packet */
 189         if (vh->h_vlan_proto != htons(ETH_P_8021Q))
 190                 return skb;
 191
 192         memmove(skb->data + VLAN_HLEN, skb->data, 2 * VLAN_ETH_ALEN);
 193
 194         eh = (struct ethhdr *)skb_pull(skb, VLAN_HLEN);
 195
 196         skb->protocol = eh->h_proto;
 197         skb->mac_header += VLAN_HLEN;
 198
 199         return skb;
 200 }
 201
 202 static struct sk_buff *modify_vlan(struct sk_buff *skb,
 203                 const struct sw_flow_key *key, const struct ofp_action *a)
 204 {
 205         uint16_t new_id = a->arg.vlan_id;
 206
 207         if (new_id != OFP_VLAN_NONE) {
 208                 if (key->dl_vlan != htons(OFP_VLAN_NONE)) {
 209                         /* Modify vlan id, but maintain other TCI values */
 210                         struct vlan_ethhdr *vh = vlan_eth_hdr(skb);
 211                         vh->h_vlan_TCI = (vh->h_vlan_TCI
 212                                         & ~(htons(VLAN_VID_MASK))) | htons(new_id);
 213                 } else  {
 214                         /* Add vlan header */
 215                         skb = vlan_put_tag(skb, new_id);
 216                 }
 217         } else  {
 218                 /* Remove an existing vlan header if it exists */
 219                 vlan_pull_tag(skb);
 220         }
 221
 222         return skb;
 223 }
 224
 225 struct sk_buff *execute_setter(struct sk_buff *skb, uint16_t eth_proto,
 226                         const struct sw_flow_key *key, const struct ofp_action *a)
 227 {
 228         switch (ntohs(a->type)) {
 229         case OFPAT_SET_DL_VLAN:
 230                 skb = modify_vlan(skb, key, a);
 231                 break;
 232
 233         case OFPAT_SET_DL_SRC: {
 234                 struct ethhdr *eh = eth_hdr(skb);
 235                 memcpy(eh->h_source, a->arg.dl_addr, sizeof eh->h_source);
 236                 break;
 237         }
 238         case OFPAT_SET_DL_DST: {
 239                 struct ethhdr *eh = eth_hdr(skb);
 240                 memcpy(eh->h_dest, a->arg.dl_addr, sizeof eh->h_dest);
 241                 break;
 242         }
 243
 244         case OFPAT_SET_NW_SRC:
 245         case OFPAT_SET_NW_DST:
 246                 modify_nh(skb, eth_proto, key->nw_proto, a);
 247                 break;
 248
 249         case OFPAT_SET_TP_SRC:
 250         case OFPAT_SET_TP_DST:
 251                 modify_th(skb, eth_proto, key->nw_proto, a);
 252                 break;
 253
 254         default:
 255                 if (net_ratelimit())
 256                         printk("execute_setter: unknown action: %d\n", ntohs(a->type));
 257         }
 258
 259         return skb;
 260 }
 261
 262 static int
 263 recv_features_request(struct sw_chain *chain, const void *msg)
 264 {
 265         const struct ofp_header *ofr = msg;
 266         return dp_send_features_reply(chain->dp, ofr->xid);
 267 }
 268
 269 static int
 270 recv_get_config_request(struct sw_chain *chain, const void *msg)
 271 {
 272         const struct ofp_header *ofr = msg;
 273         return dp_send_config_reply(chain->dp, ofr->xid);
 274 }
 275
 276 static int
 277 recv_set_config(struct sw_chain *chain, const void *msg)
 278 {
 279         const struct ofp_switch_config *osc = msg;
 280         chain->dp->config = *osc;
 281         return 0;
 282 }
 283
 284 static int
 285 recv_packet_out(struct sw_chain *chain, const void *msg)
 286 {
 287         const struct ofp_packet_out *opo = msg;
 288         struct sk_buff *skb;
 289         struct vlan_ethhdr *mac;
 290         int nh_ofs;
 291
 292         if (ntohl(opo->buffer_id) == (uint32_t) -1) {
 293                 int data_len = ntohs(opo->header.length) - sizeof *opo;
 294
 295                 /* FIXME: there is likely a way to reuse the data in msg. */
 296                 skb = alloc_skb(data_len, GFP_ATOMIC);
 297                 if (!skb)
 298                         return -ENOMEM;
 299
 300                 /* FIXME?  We don't reserve NET_IP_ALIGN or NET_SKB_PAD since
 301                  * we're just transmitting this raw without examining anything
 302                  * at those layers. */
 303                 memcpy(skb_put(skb, data_len), opo->u.data, data_len);
 304                 dp_set_origin(chain->dp, ntohs(opo->in_port), skb);
 305
 306                 skb_set_mac_header(skb, 0);
 307                 mac = vlan_eth_hdr(skb);
 308                 if (likely(mac->h_vlan_proto != htons(ETH_P_8021Q)))
 309                         nh_ofs = sizeof(struct ethhdr);
 310                 else
 311                         nh_ofs = sizeof(struct vlan_ethhdr);
 312                 skb_set_network_header(skb, nh_ofs);
 313
 314                 dp_output_port(chain->dp, skb, ntohs(opo->out_port));
 315         } else {
 316                 struct sw_flow_key key;
 317                 int n_acts;
 318
 319                 skb = retrieve_skb(ntohl(opo->buffer_id));
 320                 if (!skb)
 321                         return -ESRCH;
 322                 dp_set_origin(chain->dp, ntohs(opo->in_port), skb);
 323
 324                 n_acts = (ntohs(opo->header.length) - sizeof *opo)
 325                                 / sizeof *opo->u.actions;
 326                 flow_extract(skb, ntohs(opo->in_port), &key);
 327                 execute_actions(chain->dp, skb, &key, opo->u.actions, n_acts);
 328         }
 329         return 0;
 330 }
 331
 332 static int
 333 recv_port_mod(struct sw_chain *chain, const void *msg)
 334 {
 335         const struct ofp_port_mod *opm = msg;
 336
 337         dp_update_port_flags(chain->dp, &opm->desc);
 338
 339         return 0;
 340 }
 341
 342 static int
 343 add_flow(struct sw_chain *chain, const struct ofp_flow_mod *ofm)
 344 {
 345         int error = -ENOMEM;
 346         int n_acts;
 347         struct sw_flow *flow;
 348
 349
 350         /* Check number of actions. */
 351         n_acts = (ntohs(ofm->header.length) - sizeof *ofm) / sizeof *ofm->actions;
 352         if (n_acts > MAX_ACTIONS) {
 353                 error = -E2BIG;
 354                 goto error;
 355         }
 356
 357         /* Allocate memory. */
 358         flow = flow_alloc(n_acts, GFP_ATOMIC);
 359         if (flow == NULL)
 360                 goto error;
 361
 362         /* Fill out flow. */
 363         flow_extract_match(&flow->key, &ofm->match);
 364         flow->group_id = ntohl(ofm->group_id);
 365         flow->max_idle = ntohs(ofm->max_idle);
 366         flow->timeout = jiffies + flow->max_idle * HZ;
 367         flow->n_actions = n_acts;
 368         flow->init_time = jiffies;
 369         flow->byte_count = 0;
 370         flow->packet_count = 0;
 371         atomic_set(&flow->deleted, 0);
 372         spin_lock_init(&flow->lock);
 373         memcpy(flow->actions, ofm->actions, n_acts * sizeof *flow->actions);
 374
 375         /* Act. */
 376         error = chain_insert(chain, flow);
 377         if (error)
 378                 goto error_free_flow;
 379         error = 0;
 380         if (ntohl(ofm->buffer_id) != (uint32_t) -1) {
 381                 struct sk_buff *skb = retrieve_skb(ntohl(ofm->buffer_id));
 382                 if (skb) {
 383                         struct sw_flow_key key;
 384                         flow_used(flow, skb);
 385                         flow_extract(skb, ntohs(ofm->match.in_port), &key);
 386                         execute_actions(chain->dp, skb, &key,
 387                                         ofm->actions, n_acts);
 388                 }
 389                 else
 390                         error = -ESRCH;
 391         }
 392         return error;
 393
 394 error_free_flow:
 395         flow_free(flow);
 396 error:
 397         if (ntohl(ofm->buffer_id) != (uint32_t) -1)
 398                 discard_skb(ntohl(ofm->buffer_id));
 399         return error;
 400 }
 401
 402 static int
 403 recv_flow(struct sw_chain *chain, const void *msg)
 404 {
 405         const struct ofp_flow_mod *ofm = msg;
 406         uint16_t command = ntohs(ofm->command);
 407
 408         if (command == OFPFC_ADD) {
 409                 return add_flow(chain, ofm);
 410         }  else if (command == OFPFC_DELETE) {
 411                 struct sw_flow_key key;
 412                 flow_extract_match(&key, &ofm->match);
 413                 return chain_delete(chain, &key, 0) ? 0 : -ESRCH;
 414         } else if (command == OFPFC_DELETE_STRICT) {
 415                 struct sw_flow_key key;
 416                 flow_extract_match(&key, &ofm->match);
 417                 return chain_delete(chain, &key, 1) ? 0 : -ESRCH;
 418         } else {
 419                 return -ENOTSUPP;
 420         }
 421 }
 422
 423 /* 'msg', which is 'length' bytes long, was received from the control path.
 424  * Apply it to 'chain'. */
 425 int
 426 fwd_control_input(struct sw_chain *chain, const void *msg, size_t length)
 427 {
 428
 429         struct openflow_packet {
 430                 size_t min_size;
 431                 int (*handler)(struct sw_chain *, const void *);
 432         };
 433
 434         static const struct openflow_packet packets[] = {
 435                 [OFPT_FEATURES_REQUEST] = {
 436                         sizeof (struct ofp_header),
 437                         recv_features_request,
 438                 },
 439                 [OFPT_GET_CONFIG_REQUEST] = {
 440                         sizeof (struct ofp_header),
 441                         recv_get_config_request,
 442                 },
 443                 [OFPT_SET_CONFIG] = {
 444                         sizeof (struct ofp_switch_config),
 445                         recv_set_config,
 446                 },
 447                 [OFPT_PACKET_OUT] = {
 448                         sizeof (struct ofp_packet_out),
 449                         recv_packet_out,
 450                 },
 451                 [OFPT_FLOW_MOD] = {
 452                         sizeof (struct ofp_flow_mod),
 453                         recv_flow,
 454                 },
 455                 [OFPT_PORT_MOD] = {
 456                         sizeof (struct ofp_port_mod),
 457                         recv_port_mod,
 458                 },
 459         };
 460
 461         const struct openflow_packet *pkt;
 462         struct ofp_header *oh;
 463
 464         if (length < sizeof(struct ofp_header))
 465                 return -EINVAL;
 466
 467         oh = (struct ofp_header *) msg;
 468         if (oh->version != 1 || oh->type >= ARRAY_SIZE(packets)
 469                 || ntohs(oh->length) > length)
 470                 return -EINVAL;
 471
 472         pkt = &packets[oh->type];
 473         if (!pkt->handler)
 474                 return -ENOSYS;
 475         if (length < pkt->min_size)
 476                 return -EFAULT;
 477
 478         return pkt->handler(chain, msg);
 479 }
 480
 481 /* Packet buffering. */
 482
 483 #define OVERWRITE_SECS  1
 484 #define OVERWRITE_JIFFIES (OVERWRITE_SECS * HZ)
 485
 486 struct packet_buffer {
 487         struct sk_buff *skb;
 488         uint32_t cookie;
 489         unsigned long exp_jiffies;
 490 };
 491
 492 static struct packet_buffer buffers[N_PKT_BUFFERS];
 493 static unsigned int buffer_idx;
 494 static DEFINE_SPINLOCK(buffer_lock);
 495
 496 uint32_t fwd_save_skb(struct sk_buff *skb)
 497 {
 498         struct packet_buffer *p;
 499         unsigned long int flags;
 500         uint32_t id;
 501
 502         spin_lock_irqsave(&buffer_lock, flags);
 503         buffer_idx = (buffer_idx + 1) & PKT_BUFFER_MASK;
 504         p = &buffers[buffer_idx];
 505         if (p->skb) {
 506                 /* Don't buffer packet if existing entry is less than
 507                  * OVERWRITE_SECS old. */
 508                 if (time_before(jiffies, p->exp_jiffies)) {
 509                         spin_unlock_irqrestore(&buffer_lock, flags);
 510                         return -1;
 511                 } else
 512                         kfree_skb(p->skb);
 513         }
 514         /* Don't use maximum cookie value since the all-bits-1 id is
 515          * special. */
 516         if (++p->cookie >= (1u << PKT_COOKIE_BITS) - 1)
 517                 p->cookie = 0;
 518         skb_get(skb);
 519         p->skb = skb;
 520         p->exp_jiffies = jiffies + OVERWRITE_JIFFIES;
 521         id = buffer_idx | (p->cookie << PKT_BUFFER_BITS);
 522         spin_unlock_irqrestore(&buffer_lock, flags);
 523
 524         return id;
 525 }
 526
 527 static struct sk_buff *retrieve_skb(uint32_t id)
 528 {
 529         unsigned long int flags;
 530         struct sk_buff *skb = NULL;
 531         struct packet_buffer *p;
 532
 533         spin_lock_irqsave(&buffer_lock, flags);
 534         p = &buffers[id & PKT_BUFFER_MASK];
 535         if (p->cookie == id >> PKT_BUFFER_BITS) {
 536                 skb = p->skb;
 537                 p->skb = NULL;
 538         } else {
 539                 printk("cookie mismatch: %x != %x\n",
 540                                 id >> PKT_BUFFER_BITS, p->cookie);
 541         }
 542         spin_unlock_irqrestore(&buffer_lock, flags);
 543
 544         return skb;
 545 }
 546
 547 static void discard_skb(uint32_t id)
 548 {
 549         unsigned long int flags;
 550         struct packet_buffer *p;
 551
 552         spin_lock_irqsave(&buffer_lock, flags);
 553         p = &buffers[id & PKT_BUFFER_MASK];
 554         if (p->cookie == id >> PKT_BUFFER_BITS) {
 555                 kfree_skb(p->skb);
 556                 p->skb = NULL;
 557         }
 558         spin_unlock_irqrestore(&buffer_lock, flags);
 559 }
 560
 561 void fwd_exit(void)
 562 {
 563         int i;
 564
 565         for (i = 0; i < N_PKT_BUFFERS; i++)
 566                 kfree_skb(buffers[i].skb);
 567 }
 568
 569 /* Utility functions. */
 570
 571 /* Makes '*pskb' writable, possibly copying it and setting '*pskb' to point to
 572  * the copy.
 573  * Returns 1 if successful, 0 on failure. */
 574 static int
 575 make_writable(struct sk_buff **pskb)
 576 {
 577         /* Based on skb_make_writable() in net/netfilter/core.c. */
 578         struct sk_buff *nskb;
 579
 580         /* Not exclusive use of packet?  Must copy. */
 581         if (skb_shared(*pskb) || skb_cloned(*pskb))
 582                 goto copy_skb;
 583
 584         return pskb_may_pull(*pskb, 64); /* FIXME? */
 585
 586 copy_skb:
 587         nskb = skb_copy(*pskb, GFP_ATOMIC);
 588         if (!nskb)
 589                 return 0;
 590         BUG_ON(skb_is_nonlinear(nskb));
 591
 592         /* Rest of kernel will get very unhappy if we pass it a
 593            suddenly-orphaned skbuff */
 594         if ((*pskb)->sk)
 595                 skb_set_owner_w(nskb, (*pskb)->sk);
 596         kfree_skb(*pskb);
 597         *pskb = nskb;
 598         return 1;
 599 }