We are happy to release version 2 of the Reowolf project. This version introduces many new features: a select statement, run-time error handling, dynamic port hand-off, native TCP components and detailed project documentation. This post summarizes the most important features, and further lays out the vision we have for the future of Reowolf. This release is sponsored by the Next Generation Internet fund.

This release can be found on our Gitlab repository page. Gitlab includes an issue tracker that is open for users to submit bug reports and feature requests. The release tag is v2.0.1. The software is licensed under the MIT license.

The following aspects of the Protocol Description Language (PDL) and its supporting run-time and compiler have been improved, and in the sections below we demonstrate their functionality by small examples:

1. Select statements
2. Run-time error handling
3. Transmitting ports through ports (dynamic port hand-off)
4. Native components
5. Project documentation

Furthermore, this release has fixed a number of bugs that were present in previous releases. The final section shows the vision for the future of Reowolf.

Select statements

We have reworked the component synchronization mechanism, and the underlying consensus algorithm supporting components.

Imagine we instantiate a data_producer a number of times (say a b c), and link them up with a data_receiver. The data receiver takes a datum from one of the producers, one by one.

In the old synchronization mechanism, all data producers had to indicate they were ready to synchronize, even when only one producer actually gives data for the receiver to process. So the following example causes the inadvertent synchronization of all participating components, which causes all producing components to wait on each other:

comp data_producer(out<u64> tx, u64 min_val, u64 max_val) {
    while (true) {
        sync {
            auto value = lots_of_work(min_val, max_val);
            put(tx, value);
        }
    }
}

comp data_receiver_v1(in<u64> rx_a, in<u64> rx_b, in<u64> rx_c, u32 num_rounds) {
    u32 counter = 0;
    auto rxs = { rx_a, rx_b, rx_c };
    while (counter < num_rounds) {
        auto num_peers = length(rxs);
        auto peer_index = 0;
        while (peer_index < num_peers) {
            sync {
                auto result = get(rxs[peer_index]);
                peer_index += 1;
            }
        }
        counter += 1;
    }
}

The reason was that a synchronous interaction checked all ports for a valid interaction. So for the round robin receiver we have that it communicates with one peer per round, but it still requires the other peers to agree that they didn’t send anything at all! Note that this already implies that all running components need to synchronize. We could fix this by writing:

comp data_receiver_v2(in<u64> rx_a, in<u64> rx_b, in<u64> rx_c, u32 num_rounds) {
    u32 counter = 0;
    auto rxs = { rx_a, rx_b, rx_c };
    while (counter < num_rounds) {
        auto num_peers = length(rxs);
        auto peer_index = 0;
        sync {
            while (peer_index < num_peers) {
                auto result = get(rxs[peer_index]);
                peer_index += 1;
            }
        }
        counter += 1;
    }
}

But this is not the intended behavior. We want the producer components to be able to run independently of one another. This requires a change in the semantics of the language! We no longer have that each peer is automatically dragged into the synchronous round. Instead, after the first message of the peer is received through a get call, will we merge each other’s synchronous rounds.

With such a change to the runtime, we now have that the first version (written above) produces the intended behavior: the consumer accepts one value and synchronizes with its sender. Then it goes to the next round and synchronizes with the next sender.

But what we would really like to do is to synchronize with any of the peers that happens to have its work ready for consumption. And so the select statement is introduced into the language. This statement can be used to describe a set of possible behaviors we could execute. Each behavior will have an associated set of ports. When those associated set of ports have a message ready to be read, then the corresponding behavior will execute. So to complete the example above, we have:

comp data_receiver_v3(in<u64> rx_a, in<u64> rx_b, in<u64> rx_c, u32 num_rounds) {
    u32 counter = 0;
    auto rxs = { rx_a, rx_b, rx_c };

    u32 received_from_a = 0;
    u32 received_from_b_or_c = 0;
    u32 received_from_a_or_c = 0;
    u64 sum_received_from_c = 0;

    while (counter < num_rounds*3) {
        sync {
            select {
                auto value = get(rx_a) -> {
                    received_from_a += 1;
                    received_from_a_or_c += 1;
                }
                auto value = get(rx_b) -> {
                    received_from_b_or_c += 1;
                }
                auto value = get(rx_c) -> {
                    received_from_a_or_c += 1;
                    received_from_b_or_c += 1;
                    sum_received_from_c += value;
                }
            }
        }
        counter += 1;
    }
}

Run-time error handling

We have an initial implementation for error handling and reporting. Roughly speaking: if a component has failed then it cannot complete any current or future synchronous rounds anymore. Hence, apart from some edge cases, any (attempted) received message by a peer should cause a failure at that peer as well. We may have a look at the various places where a component can crash, and how its neighboring peer handles receiving messages: sometimes the crash of the first component propagates, and sometimes it is blocked.

enum ErrorLocation {
    BeforeSync,
    DuringSyncBeforeFirstInteraction,
    DuringSyncBeforeSecondInteraction,
    DuringSyncAfterInteractions,
    AfterSync,
}

func crash() -> u8 {
    return {}[0]; // access index 0 of an empty array
}

comp sender_and_crasher(out<u32> value, ErrorLocation loc) {
    if (loc == ErrorLocation::BeforeSync) { crash(); }
    sync {
        if (loc == ErrorLocation::DuringSyncBeforeFirstInteraction) { crash(); }
        put(value, 0);
        if (loc == ErrorLocation::DuringSyncBeforeSecondInteraction) { crash(); }
        put(value, 1);
        if (loc == ErrorLocation::DuringSyncAfterInteractions) { crash(); }
    }
    if (loc == ErrorLocation::AfterSync) { crash(); }
}

comp receiver(in<u32> value) {
    sync {
        auto a = get(value);
        auto b = get(value);
    }
}

comp main() {
    channel tx -> rx;

    new sender_and_crasher(tx, ErrorLocation::AfterSync);
    new receiver(rx);
}

Note that when we run the example with the error location before sync, or during sync, that the receiver always crashes. However the location where it will crash is somewhat random! Due to the asynchronous nature of the runtime, a sender of messages will always just put the value onto the port and continue execution. So even though the sender component might already be done with its sync round, the receiver officially still has to receive its first message. In any case, a neat error message is displayed in the console (or in some other place where such diagnostics are reported).

Note that, especially, given the asynchronous nature of the runtime, the receiver should figure out when the peer component has crashed, but it can still finish the current synchronous round. This might happen if the peer component crashes just after the synchronous round. However, there may be a case where the peer receives the information that the peer crashed before it receives the information that the synchronous round has succeeded.

Transmitting ports through ports

Since this release transmitting ports is possible. This means that we can send ports through ports. In fact, we can send ports that may send ports that may send ports, etc. But don’t be fooled by the apparent complexity. The inner type T of a port like in<T> simply states that that is the message type. Should the type T contain one or more ports, then we kick off a bit of code that takes care of the transfer of the port. Should the port inside of T itself, after being received, send a port, then we simply kick off that same procedure again.

In the simplest case, we have someone transmitting the receiving end of a channel to another component, which then uses that receiving end to receive a value. The example below shows this:

comp port_sender(out<in<u32>> tx, in<u32> to_transmit) {
    sync put(tx, to_transmit);
}

comp port_receiver_and_value_getter(in<in<u32>> rx, u32 expected_value) {
    u32 got_value = 0;
    sync {
        auto port = get(rx);
        got_value = get(port);
    }
    if (expected_value == got_value) {
        print("got the expected value :)");
    } else {
        print("got a different value :(");
    }
}

comp value_sender(out<u32> tx, u32 to_send) {
    sync put(tx, to_send);
}

comp main() {
    u32 value = 1337_2392;

    channel port_tx -> port_rx;
    channel value_tx -> value_rx;
    new port_sender(port_tx, value_rx);
    new port_receiver_and_value_getter(port_rx, value);
    new value_sender(value_tx, value);
}

Of course we may do something a little more complicated than this. Suppose that we don’t just send one port, but send a series of ports. i.e. we use an Option union type, to turn an array of ports that we’re going to transmit into a series of messages containing ports, each sent to a specific component.

union Option<T> {
    Some(T),
    None,
}

comp port_sender(out<Option<in<u32>>>[] txs, in<u32>[] to_transmit) {
    auto num_peers = length(txs);
    auto num_ports = length(to_transmit);

    auto num_per_peer = num_ports / num_peers;
    auto num_remaining = num_ports - (num_per_peer * num_peers);

    auto peer_index = 0;
    auto port_index = 0;
    while (peer_index < num_peers) {
        auto peer_port = txs[peer_index];
        auto counter = 0;

        // Distribute part of the ports to one of the peers.
        sync {
            // Sending the main batch of ports for the peer
            while (counter < num_per_peer) {
                put(peer_port, Option::Some(to_transmit[port_index]));
                port_index += 1;
                counter += 1;
            }

            // Sending the remainder of ports, one per peer until they're gone
            if (num_remaining > 0) {
                put(peer_port, Option::Some(to_transmit[port_index]));
                port_index += 1;
                num_remaining -= 1;
            }

            // Finish the custom protocol by sending nothing, which indicates to
            // the peer that it has received all the ports we have to hand out.
            put(peer_port, Option::None);
        }

        peer_index += 1;
    }
}

And here we have the component which will receive on that port. We can design the synchronous regions any we want. In this case when we receive ports we just synchronize port_sender, but the moment we receive messages we synchronize with everyone.

comp port_receiver(in<Option<in<u32>>> port_rxs, out<u32> sum_tx) {
    // Receive all ports
    auto value_rxs = {};

    sync {
        while (true) {
            auto maybe_port = get(port_rxs);
            if (let Option::Some(certainly_a_port) = maybe_port) {
                value_rxs @= { certainly_a_port };
            } else {
                break;
            }
        }
    }

    // Receive all values
    auto received_sum = 0;

    sync {
        auto port_index = 0;
        auto num_ports = length(value_rxs);
        while (port_index < num_ports) {
            auto value = get(value_rxs[port_index]);
            received_sum += value;
            port_index += 1;
        }
    }

    // And send the sum
    sync put(sum_tx, received_sum);
}

Now we need something to send the values, we’ll make something incredibly simple. Namely:

comp value_sender(out<u32> tx, u32 value_to_send) {
    sync put(tx, value_to_send);
}

comp sum_collector(in<u32>[] partial_sum_rx, out<u32> total_sum_tx) {
    auto sum = 0;
    auto index = 0;
    while (index < length(partial_sum_rx)) {
        sync sum += get(partial_sum_rx[index]);
        index += 1;
    }
    sync put(total_sum_tx, sum);
}

And we need the component to set this entire system of components up. So we write the following entry point.

comp main() {
    auto num_value_ports = 32;
    auto num_receivers = 3;

    // Construct the senders of values
    auto value_port_index = 1;
    auto value_rx_ports = {};
    while (value_port_index <= num_value_ports) {
        channel value_tx -> value_rx;
        new value_sender(value_tx, value_port_index);
        value_rx_ports @= { value_rx };
        value_port_index += 1;
    }

    // Construct the components that will receive groups of value-receiving
    // ports
    auto receiver_index = 0;
    auto sum_combine_rx_ports = {};
    auto port_tx_ports = {};

    while (receiver_index < num_receivers) {
        channel sum_tx -> sum_rx;
        channel port_tx -> port_rx;
        new port_receiver(port_rx, sum_tx);

        sum_combine_rx_ports @= { sum_rx };
        port_tx_ports @= { port_tx };
        receiver_index += 1;
    }

    // Construct the component that redistributes the total number of input
    // ports.
    new port_sender(port_tx_ports, value_rx_ports);

    // Construct the component that computes the sum of all sent values
    channel total_value_tx -> total_value_rx;
    new sum_collector(sum_combine_rx_ports, total_value_tx);

    auto expected = num_value_ports * (num_value_ports + 1) / 2;
    auto received = 0;

    sync received = get(total_value_rx);

    if (expected == received) {
        print("got the expected value!");
    } else {
        print("got something entirely different");
    }
}

Native TCP components

Also new in this release are native components. Native components are provided by the underlying implementation of Reowolf and allow protocols to be built on top of other protocols. We demonstrate this by introducing native components for the Transmission Control Protocol (TCP). Hence, Reowolf can now be used to express protocols that assume an underlying implementation of TCP.

We’ll start by important the standard library that defines the builtin components that support a TCP listener and a TCP client. We’ll define a little utility function (listen_port) that is used through this example that is called to retrieve the port we’re going to listen on.

import std.internet::*;

func listen_port() -> u16 {
    return 2392;
}

Next we define our server. The server accepts (for the case of this example) a number of connections until it will stop listening. At that point it will wait until it receives a signal that allows it to shut down.

comp server(u32 num_connections, in<()> shutdown) {
    // Here we set up the channels for commands, going to the listener
    // component, and the channel that sends new connections back to us.
    channel listen_cmd_tx -> listen_cmd_rx;
    channel listen_conn_tx -> listen_conn_rx;

    // And we create the tcp_listener, imported from the standard library, here.
    new tcp_listener({}, listen_port(), listen_cmd_rx, listen_conn_tx);

    // Here we set up a variable that will hold our received connections
    channel client_cmd_tx -> unused_client_cmd_rx;
    channel unused_client_data_tx -> client_data_rx;
    auto new_connection = TcpConnection{
        tx: client_cmd_tx,
        rx: client_data_rx,
    };

    auto connection_counter = 0;
    while (connection_counter < num_connections) {
        // We wait until we receive a new connection
        sync {
            // The way the standard library is currently written, we need to
            // send the `tcp_listener` component the command that it should
            // listen to for the next connection. This is only one way in which
            // the standard library could be written. We could also write it
            // such a way such that a separate component buffers new incoming
            // connections, such that we only have to `get` from that separate
            // component.
            //
            // Note that when we get such a new connection, (see the
            // TcpConnection struct in the standard library), the peers of the
            // two ports are already hooked up to a `tcp_client` component, also
            // defined in the standard library.
            put(listen_cmd_tx, ListenerCmd::Accept);
            new_connection = get(listen_conn_rx);
        }

        // In any case, now that the code is here, the synchronous round that
        // governed receiving the new connection has completed. And so we send
        // that connection off to a handler component. In this case we have the
        // `echo_machine` component, defined in this file as well.
        new echo_machine(new_connection);
        connection_counter += 1;
    }

    // When all of the desired connections have been handled, we first await a
    // shutdown signal from another component.
    sync auto v = get(shutdown);

    // And once we have received that signal, we'll instruct the listener
    // component to shut down.
    sync put(listen_cmd_tx, ListenerCmd::Shutdown);
}

The following piece of code represents the component that is spawned by the server component to handle new connections. All it does is wait for a single incoming TCP packet, where it expects a single byte of data, and then echo that back to the peer.

comp echo_machine(TcpConnection conn) {
    auto data_to_echo = {};

    // Here is where we receive a message from a peer ...
    sync {
        put(conn.tx, ClientCmd::Receive);
        data_to_echo = get(conn.rx);
        put(conn.tx, ClientCmd::Finish);
    }

    // ... and send it right back to our peer.
    sync put(conn.tx, ClientCmd::Send(data_to_echo));

    // And we ask the `tcp_client` to shut down neatly.
    sync put(conn.tx, ClientCmd::Shutdown);
}

// Here is the component that we will instantiate to connect to the `server`
// component above (more specifically, to the `tcp_listener` component
// instantiated by the `server`). This is the component that will ask the
// `echo_machine` component to echo a byte of data.

comp echo_requester(u8 byte_to_send, out<()> done) {
    // We instantiate the `tcp_client` from the standard library. This will
    // perform the "connect" call to the `tcp_listener`.
    channel cmd_tx -> cmd_rx;
    channel data_tx -> data_rx;
    new tcp_client({127, 0, 0, 1}, listen_port(), cmd_rx, data_tx);

    // And once we are connected, we send the single byte to the other side.
    sync put(cmd_tx, ClientCmd::Send({ byte_to_send }));

    // This sent byte will arrive at the `echo_machine`, which will send it
    // right back to us. So here is where we wait for that byte to arrive.
    auto received_byte = byte_to_send + 1;
    sync {
        put(cmd_tx, ClientCmd::Receive);
        received_byte = get(data_rx)[0];
        put(cmd_tx, ClientCmd::Finish);
    }

    // We make sure that we got back what we sent
    if (byte_to_send != received_byte) {
        crash();
    }

    // And we shut down the TCP connection
    sync put(cmd_tx, ClientCmd::Shutdown);

    // And finally we send a signal to another component (the `main` component)
    // to let it know we have finished our little protocol.
    sync put(done, ());
}

And here the entry point for our program:

comp main() {
    // Some settings for the example
    auto num_connections = 12;

    // We create a new channel that allows us to shut down our server component.
    // That channel being created, we can instantiate the server component.
    channel shutdown_listener_tx -> shutdown_listener_rx;
    new server(num_connections, shutdown_listener_rx);

    // Here we create all the requesters that will ask their peer to echo back
    // a particular byte.
    auto connection_index = 0;
    auto all_done = {};
    while (connection_index < num_connections) {
        channel done_tx -> done_rx;
        new echo_requester(cast(connection_index), done_tx);
        connection_index += 1;
        all_done @= {done_rx};
    }

    // Here our program starts to shut down. First we'll wait until all of our
    // requesting components have gotten back the byte they're expecting.
    auto counter = 0;
    while (counter < length(all_done)) {
        sync auto v = get(all_done[counter]);
        counter += 1;
    }

    // And we shut down our server.
    sync put(shutdown_listener_tx, ());
}

Project documentation

Detailed documentation has been provided, providing users and developers background information about the current implementation of Reowolf 2.

• The Runtime Design documents the general architecture, the Reowolf run-time, design decisions, control algorithms, dealing with crashing components, and synchronization.
• A new version of the consensus algorithm. Also the previous implementation of the consensus algorithm (which is replaced to implement the select statement) is documented.

Developers interested in contributing to the Reowolf project are invited to read the Known Issues document. These offer various known limitations in the implementation, ranging from small issues to large issues. Pull requests are welcome!

What is ahead?

After this release we continue our work in the following directions:

• Further ahead is improvements to the native component libraries, and starting to model existing Internet protocols such as BGP that builds on top of the TCP protocol.
• We are interested in the SCION internet architecture, and are investigating whether the Reowolf connector API can be used for programming internet applications that run on top of SCION, and whether we can specify components in PDL that allow applications to make use of all capabilities SCION networks offer. Towards this, we are setting up a subnet that will be connected to the SCIONlab network. Our experiences will be published in a series of blog posts.
• We decided to wait a bit longer before we start work on integrating Reowolf into the operating system kernel. Although we are exploring which operating system is most suitable for integration, we have not yet reached a stable protocol description language.
• Work on the specification of the Protocol Description Language (PDL), leading to a standardization track. Part of this specification work is the need to formalize, in an unambiguous manner, the semantics of protocols specified in PDL.
• Work on formal verification of protocol specified in PDL. We have received funding from NLnet / NGI ASSURE for continuing the project in this direction. More about this topic soon!

We will keep you updated!

The Reowolf Team
– May 20, 2022