A Functional Router,
with Mirage and OpenFlow
CHANGE/OFELIA Summer School 2011, Berlin, Germany
CHANGE/OFELIA Summer School 2011, Berlin, Germany
Borrowing heavily from the CUFP 2011 tutorial by Anil Madhavapeddy, David Scott, Thomas Gazagnaire, Raphael Proust, Balraj Singh, and Richard Mortier..
Topic | Activity | Time |
---|---|---|
What is Mirage? | Presentation | 10 min |
What is OCaml? | Presentation | 10 min |
Hello World! | Activity | 15 min |
Stretch | ||
Threading | Presentation | 10 min |
Threading Demo | Activity | 15 min |
Comfort Break | 5 min | |
Networking | Presentation | 10 min |
Networking Demo | Activity | 15 min |
Stretch | ||
OpenFlow Protocol | Presentation | 10 min |
OpenFlow Controller & Switch | Presentation | 10 min |
OpenFlow Demo | Activity | 10 min |
Anil Madhavapeddy
mir-build is a wrapper over ocamlbuild.
Output files are in _build/ and source is never modified.
All of this build-time synthesis is wrapped by the powerful ocamlbuild, which supports dynamic dependencies.
Mirage also has extra rules. Prepend the backend name to your target:
$ cd mirage-tutorial/examples/hello $ mir-build unix-direct/hello.bin $ mir-build unix-socket/hello.bin $ mir-build xen/hello.xen # need Linux x86_64 $ mir-build node/hello.js # need js_of_ocaml $ mir-run -b unix-socket _build/unix-socket/hello.bin $ mir-run -b unix-direct _build/unix-direct/hello.bin $ mir-run -b node _build/node/hello.js $ mir-run -b xen _build/xen/hello.xen
Richard Mortier
Additionally, most variables are immutable, and everything is an expresssion, i.e., returns a value.
let binds names to expressions, rather like declaring variables and functions:
let x = 1 ;; let f x y = x + y ;;
It also declares recursive functions:
let rec pow x y = if y = 0 then 1 else x * pow x (y-1)
And it can be nested:
let result = let x, y = 1, 10 in let z = 100 in x+y+z ;;
Due to its typing rules, OCaml will infer the types of your expressions. This is helpful! Not only does it reduce typing, it catches bugs at compile time.
There are 6 primitive types: int, float, char, string, bool, unit. The first five behave in the way you’d expect:
let c = 'c' ;; let s = "s" ^ "t" ^ "r" ^ "i" ^ "n" ^ "g" ;; let yes = true ;; let ten = 1 + 9 ;; let point_five = 1. /. 2. ;;N.B. Notice no automatic type conversion, and the lack of polymorphic arithmetic operators.
# let f = fun x -> fun y -> x + y ;; val f : int -> int -> int = <fun> # f 1 10;; - : int = 11
This can be abbreviated:
# let f x y = x + y ;; val f : int -> int -> int = <fun> # f 1 10;; - : int = 11
Note that function application does not require parentheses around arguments:
let f x y = x + y in f x y ;;
unit is the singleton type, i.e., it contains only one value, (). Think of it like void in C. It often represents the value of expressions with side-effects.
Printf.printf "this returns unit" ;;
'a, 'b, and so on are used when an expression is parameterized by type — parametric polymorphism:
# let identity x = x ;; val identity : 'a -> 'a = <fun> # identity 10 ;; - : int = 10 # identity "s" ;; - : string = "s" # identity 'c' ;; - : char = 'c'
Tuples are fixed-length lists with fields of mixed types:
let t = (2, "str", 10.2) ;;
Lists have operations to append and cons but have all fields of the same type:
let x = [2;3] in let cons = 1 :: x in let append = x @ cons ;;
Records are tuples with labelled fields, which may be mutable:
type r = { one: int; two: string; mutable three: float } ;; let one = 1 in let r = { one; two="two"; three=1.0 } ;; r.three <- 11.0 ;;
Variant types are similar to union types in C:
type 'a option = | None | Some of 'a ;;
Pattern matching is very widely used in OCaml with constants, variables, variant types, records. The syntax is surprisingly flexible and concise:
let rec llen l = match l with | [] -> 0 | x :: y -> 1 + llen y ;; let rec llen = function | [] -> 0 | x :: y -> 1 + llen y ;;
OCaml has a rich module system, and Mirage makes a set of standard modules available by default. For example:
open Openflow ;; module OP = Openflow.Ofpacket ;; let process_of_packet st (rem_addr, rem_port) p t = OP.( match p with | Hello (h, _) -> send_packet t (Header.build_h h) | Echo_req (h, bits) -> send_packet t (build_echo_response h bits) | ... )
Raphael Proust, Balraj Singh and Anil Madhavapeddy
Let’s look at some examples.
They are all in
mirage-tutorial/examples/lwt, and you build them by:
$ mir-build unix-socket/sleep.bin $ ./_build/unix-socket/sleep.bin
More tutorial content is available at:
http://openmirage.org/wiki/tutorial-lwt (this tutorial)
http://ocsigen.org/lwt/manual/ (Lwt manual)
val return : 'a -> 'a Lwt.t
Lwt.return v builds a thread that returns with value v.
val bind : 'a Lwt.t -> ('a -> 'b Lwt.t) -> 'b Lwt.t
Lwt.bind t f creates a thread which waits for t to terminate, then pass the result to f. If t is a sleeping thread, then bind t f will sleep too, until t terminates.
val join : unit Lwt.t list -> unit Lwt.t
Lwt.join takes a list of threads and waits for them all to terminate.
Lwt.bind (OS.Time.sleep 1.0) (fun () -> Lwt.bind (OS.Time.sleep 2.0) (fun () -> OS.Console.log "Wake up sleepy!\n"; Lwt.return () ) )
More natural ML style, via syntax extension:
lwt () = OS.Time.sleep 1.0 in lwt () = OS.Time.sleep 2.0 in OS.Console.log "Wake up sleepy!\n"; Lwt.return ()
lwt/sleep.ml (make sleep)
lwt () = OS.Time.sleep 1.0 in lwt () = OS.Time.sleep 2.0 in OS.Console.log "Wake up sleepy!\n"; Lwt.return ()
After syntax transform: (make sleep.pp)
let __pa_lwt_0 = OS.Time.sleep 1.0 in Lwt.bind __pa_lwt_0 (fun () -> let __pa_lwt_0 = OS.Time.sleep 2.0 in Lwt.bind __pa_lwt_0 (fun () -> (OS.Console.log "Wake up sleepy!\n"; Lwt.return () ) ) )
The scheduler is itself written in OCaml, but is operating system specific. To consider UNIX:
let t,u = Lwt.task () in // t sleeps forever Lwt.wakeup u "foo"; // and u can wake it up t // value carried by t is "foo"
The outside world wakes up sleeping threads via the Lwt.wakeup mechanism:
Raphael Proust, Balraj Singh and Anil Madhavapeddy
Write a program that spins off two threads, each of which sleeps for some amount of time, say 1 and 2 seconds respectively, and then one prints “Heads”, and the other “Tails”.
After both have finished, print “Finished” and exits.
$ cd mirage-tutorial/examples/lwt $ vim mysleep.ml $ make mysleep # answer is in sleep.ml
Write an echo server that reads from a dummy input generator and writes each input read to the console. The server should stop listening after 10 inputs are received.
$ cd mirage-tutorial/examples/lwt $ vim myecho1.ml $ make myecho1 # answer is in echo1.ml
You can use this function as a traffic generator:
let read_line () = OS.Time.sleep (Random.float 1.5) >> Lwt.return (String.make (Random.int 20) 'a')
Anil Madhavapeddy, Thomas Gazagnaire and David Scott
I/O is platform-specific, and exposed via OS.Blkif and OS.Netif . Each platform has a different low-level implementation behind the same signatures:
The interface for OS.Ring is quite generic.
type sring module Front : sig // 'a is the response type, and 'b is the request id type ('a,'b) t val init : sring:sring -> ('a,'b) t val slot : ('a,'b) t -> int -> Bitstring.t val nr_ents : ('a,'b) t -> int val get_free_requests : ('a,'b) t -> int val next_req_id: ('a,'b) t -> int val ack_responses : ('a,'b) t -> (Bitstring.t -> unit) -> unit val push_requests : ('a,'b) t -> unit val push_requests_and_check_notify : ('a,'b) t -> bool end
The source code has more comments!
lib/os/xen/blkif.ml: Io_page.with_page (* allocate 4KiB page *) (fun () -> Gnttab.with_grant (* allow backend to read it *) (fun () -> Ring.Front.push_request... Evtchn.notify ... ...
type features = { sg: bool; gso_tcpv4: bool; rx_copy: bool; rx_flip: bool; smart_poll: bool; }
Let’s dive straight in, and bring up the Mirage network stack on UNIX. You will need tuntap on your OS (Linux or MacOS X).
The bridge should have IP 10.0.0.1 as the applications default to 10.0.0.2. Try not to bridge to the outside network!
$ cd mirage-tutorial/examples/net/ping $ mir-build unix-direct/ping.bin $ sudo ./_build/unix-direct/ping.bin // Another terminal $ ping 10.0.0.2
You should receive ICMP echo replies from the Mirage network stack !
module type DATAGRAM = sig type mgr type src type dst type msg val recv : mgr -> src -> (dst -> msg -> unit Lwt.t) -> unit Lwt.t val send : mgr -> ?src:src -> dst -> msg -> unit Lwt.t end module UDPv4 : Nettypes.DATAGRAM with type mgr = Manager.t and type src = Nettypes.ipv4_src and type dst = Nettypes.ipv4_dst and type msg = Bitstring.t
$ cd mirage-tutorial/examples/dns $ make # different terminal $ dig @127.0.0.1 -p 5555 www.openmirage.org $ dig @127.0.0.1 -p 5555 txt www.openmirage.org
This builds the socket version, listening on port 5555 and localhost.
It uses UNIX kernel sockets and not the Mirage stack (useful for testing the higher level protocols).
New concept is Bitstring.t, from the Bitstring library by Richard Jones. It lets us avoid copying strings.
type bitstring = string * int * int
A bitstring is a tuple of the string and an offset (in bits) and length (in bits) into that string.
I/O is often expressed as a stream of bitstring and can be converted to an OCaml string via Bitstring_stream:
type bitstream = Bitstring.t Lwt_stream.t module Bitstring_stream : sig val string_of_stream : bitstream -> string Lwt.t
Used in most protocols. Below is the OpenFlow message header from the OpenFlow protocol :
let parse_h bits = (bitmatch bits with | { 1:8:int; t:8; len:16; xid:32 } -> { ver=byte 1; ty=msg_code_of_int t; len; xid } | { _ } -> raise (Unparsable ("parse_h", bits)) )
Richard Mortier, Haris Rotsos
Following the standard OpenFlow model — of switch, protocol, controller — the implementation comprises three parts:
N.B. There are two versions of the OpenFlow protocol: v1.0.0 (0x01 on the wire) and v1.1.0 (0x02 on the wire). The implementation supports wire protocol 0x01 as this is what is implemented in Open vSwitch used for debugging.
Contains readers/writers for the OpenFlow protocol, organized into modules following the v1.0.0 specification.
The next few slides will look briefly at these modules.
Packet_in where a packet arrives at the switch and is forwarded to the controller, either due to lack of matching entry, or an explicit action.
Packet_out indicates that a buffered packet must now have actions performed on it, typically culminating in it being forward out of one or more ports.
Flow_mod, Port_mod represent modification messages to existing flow and port state in the switch.
Stats contains structures representing the different statistics messages available through OpenFlow, as well as the request and response messages that transport them.
This is a skeleton controller similar to NOX, providing a simple event based wrapper around the OpenFlow protocol, e.g.,
Also supported are FLOW_REMOVED, FLOW_STATS_REPLY, AGGR_FLOW_STATS_REPLY, DESC_STATS_REPLY, PORT_STATS_REPLY, TABLE_STATS_REPLY, PORT_STATUS.
The controller state is mutable and modelled as:
listen is the main entry point to the controller, which creates a receiving channel to parse OpenFlow packets and pass them to process_of_packet which processes each received packet within the context of the switch’s current state. This handles protocol-level interactions, and generates necessary Mirage events.
Logically, an OpenFlow switch or datapath consists of one or more flow tables, and a secure channel back to the controller.
Communication over the channel is via the OpenFlow protocol, and is how the controller manages the switch.
Each flow table contains flow entries consisting of match fields, counters, and instructions to apply to packets.
Starting with the first flow table, if an incoming packet matches an entry, the counters are updated and the instructions carried out. If no entry in the first table matches, (part of) the packet is forwarded to the controller, or it is dropped, or it proceeds to the next flow table.
Entry represents a single flow table entry. Each consists of:
Table representing a table of flow entries. Currently just an id (tid) and a list of entries (Entry.t list).
Encapsulates the switch (or datapath) itself. Currently defines a
port as:
The switch is then modelled as:
Richard Mortier, Haris Rotsos