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