Transmit different protobuf message types

[mickvangelderen]

Why are we using protobuf?

We are using protobuf so that we can add fields to messages, even if we already have some existing messages that we still want to be able to use, without having to convert them to the new format.

Protobuf also lets us generate source files for a number of programming languages from a message specification. This means we don't have to port specialized encoding/decoding functions to multiple languages.

Another benefit of protobuf, for which we do not necessarily need protobuf, is that it always encodes numbers as little endian and provides varint encoding.

What do we want to achieve?

Eventually we want to send messages back and forth between the embedded and desktop application. Different types of messages will be sent at different frequencies. From the perspective of the micro controller we want to report sensor values, simulation state, system configuration (code revision, timer clock frequencies), errors and respond to action or configuration commands. There are probably more uses than the ones I just enumerated.

Limitations

We do not use dynamic memory allocation on the micro-controller.

Challenges

Message framing

We use Consistent Overhad Byte Stuffing (COBS) to frame messages. COBS takes a specific byte value (0x00 in our case) and removes it from the message data so it can be used as a marker.

Skipping over a messages means reading until the next 0x00 byte. This is slower than if we would prepend the length of the message. However when prepending the message length it would become hard to recover reading from the middle of a message. A combination is possible and currently employed.

Message types

Protobuf does not provide message differentiation. It expects you to know what kind of messages is coming when decoding. This is highlighted in the documentation. However

The suggestion they make here does not seem to apply to protobuf 3. Protobuf encodes the fields of a message by writing the tag of the field (a number) and the value. By creating an enumeration that does exactly that, you are doing things twice unnecessarily.

nanopb has documentation on this subject. They suggest specifying a number for each message type which can then be accessed through the generated C header. This message identifying number can be specified as an nanopb option which I assume is not compatible with the C# generator plugin. This means we would have to expose and connect the message type identifiers to message types manually for the C# code and keep it in sync with the nanopb specific protobuf definition options. Edit: perhaps we can access the msgid option from C# if the generated source provides reflection on custom options.

My most recent suggestion was to let protobuf do the work for us. Simply have a "Master" message with all fields optional (proto3 only supports optional fields anyway, for good reason) defining the different types of messages.

syntax = "proto3";

message Master {
  message Configuration {
    string commit = 1;
    int32 timer_frequency_hz = 2;
  }

  Configuration configuration = 1;

  message State {
    int32 x = 1;
    int32 y = 2;
  }

  State state = 2;
}

Then in your message handling code, simply check if any of the fields are present and process them. This approach uses a lot of memory on the micro-controller however because we use static allocation. Space must be allocated for all optional messages. Also I don't think nanopb handles optional fields nicely. I am under the impression that the fields are simply set to the default value of the type (zero usually) when they are not present.

Perhaps using the nanopb msgid approach makes the embedded side easier/more efficient. Perhaps we should look into dynamic memory allocation. Perhaps we can work around the static allocation limitation in the serial connection thread quite easily by having only 1 master struct and separate queues for message types with a length respecting the transmission frequency.

Implementing asynchronous transmission

I have a general idea of how this should be done but no actual experience. The challenge lies in efficiently sharing data with limited memory capacity, not slowing down the simulation thread, dealing with overflowing, transmitting and allowing receiving messages to be supported in the future.

[oliverlee]

Message types

My most recent suggestion was to let protobuf do the work for us. Simply have a "Master" message with all fields optional (proto3 only supports optional fields anyway, for good reason) defining the different types of messages.

If we only allow one optional field per message, we could use oneof:
https://developers.google.com/protocol-buffers/docs/proto#oneof
https://jpa.kapsi.fi/nanopb/docs/concepts.html#oneof
However this isn't supported by protobuf-net (protobuf-net/protobuf-net#47). If the C# version of protobuf can be used with Unity (I thought it couldn't as it uses an earlier and limited version of .NET), then switching proto3 should be fairly straightforward.

Perhaps using the nanopb msgid approach makes the embedded side easier/more efficient. Perhaps we should look into dynamic memory allocation. Perhaps we can work around the static allocation limitation in the serial connection thread quite easily by having only 1 master struct and separate queues for message types with a length respecting the transmission frequency.

I'm not sure how dynamic memory allocation would help. If we instantiate a Master message, memory will be allocated for all optional submessages. Possibly we could avoid this by doing some of the encoding ourselves and only instantiating the submessage being used.

If dynamic memory is necessary, I would prefer to avoid having a real heap. An alternative is to use a memory pool which should be sufficient as we know the allocated object size and should be able to tune the pool size : https://en.wikipedia.org/wiki/Memory_pool
ChibiOS implementation documentation here: http://chibios.sourceforge.net/docs3/rt/group__pools.html

As for msgid, there's a a discussion here:
https://groups.google.com/forum/#!searchin/nanopb/msgid/nanopb/TWm3vd1bJIg/3xcte_DiTSwJ

Asynchronous transmission

I imagine we have a serial transmit thread (ignore receive thread for now as I imagine the implementation would differ) which contains two message queues:

• low frequency, high priority (HP) message queue: pose used for visualization
• high frequency, low priority (LP) message queue: simulation state, configuration, etc.

The HP queue would ideally have one element; we only care about the most recent pose as we draw this in real-time (or attempt to). The LP queue could overwrite or ignore messages if full; ideally the size is chosen to avoid overflow. Since the state messages have a timestamp and are generated at a periodic interval, we can detect queue overflow when processing the data.

The best way to manage memory of objects in the LP is the use of mailboxes in conjunction with a memory pool: http://www.chibios.org/dokuwiki/doku.php?id=chibios:book:kernel_mailboxes
http://chibios.sourceforge.net/docs3/rt/group__mailboxes.html
Note that a Chibios message msg_t is essentially a data pointer. We would have this point to the associated object in the memory pool and enforce synchronization between the two.

Giovanni implemented this a "mail pool" at one time, but it has since been removed:
http://www.chibios.com/forum/viewtopic.php?t=366

[oliverlee]

Another note on asynchronous transmission

In this model, we have threads that produce messages (simulation thread, kinematics thread) and another thread that consumes messages (serial transmission thread). We may have another way to consume messages: imagine a logging thread (which will be required for the steer-by-wire project) that writes messages to disk.

[oliverlee]

This also addresses #173 #87

[mickvangelderen]

If the C# version of protobuf can be used with Unity (I thought it couldn't as it uses an earlier and limited version of .NET), then switching proto3 should be fairly straightforward.

Instructions on configuring the project to target .NET 3.5 are provided. The build instructions are missing from the documentation. Tried linux with .NET Core first but couldln't get it to work. Then switched to Windows and tried opening the Visual Studio solution. Got quite a few errors, couldn't fix them. Then figured something out using the dotnet command. Ran the following using the terminal that comes with git for windows.

git clone [email protected]:google/protobuf.git
git checkout v3.3.0
cd csharp/src
vim Google.Protobuf/project.json # add `"net35": {},` to the `"frameworks"` object
dotnet restore # this command might fail and that might be okay
dotnet build -c Release Google.Protobuf

Added the built assembly to a toy Unity project and it wasn't complaining. Seems like we can use proto 3. Instead of having to switch to windows when updating the .proto files we only have to switch to windows to build updated protobuf assemblies.

[mickvangelderen]

protobuf-3.3.0-net35.zip

[mickvangelderen]

Message Types

oneof (variant) code

• ❌ Memory object size: maximum size of all variants + int to denote which variant
• 👍 Transfer object size: size of variant + something for the variant denoting field
• 👍 Available cross language

enum code

• 👍 Memory object size: size of specific variant + int for the enum
• 👍 Transfer object size: size of variant + varint for the enum
• 👍 Available cross language

msgid code

• ❌ Not available cross language. Checked it by inspecting the generated C# reflection code.

Conclusion

The msgid approach does not work for us. The oneof approach is identical to the enum approach apart from the fact that it forces a master union struct and does not expose the type enum nicely. For me simply encoding an enum value before the message of the corresponding enum type is the way to go. We are already doing something like this since we are prepending the message size.

[oliverlee]

oneof

This appears to be exactly what we want.

enum

We would still need to store the data in addition to the enum value.

msgid

This is nanopb specific and we would have to implement it for C++ and C#.

Not sure if you just skipped if for the experiment blobs, but the nanopb option max_size (or max_length) should be defined for a string field type so that the maximum message size is known at compile time.

[mickvangelderen]

@oliverlee updated the message type analysis.

[oliverlee]

How are you proposing we use enum? The way I see it being used is:

...[enum.A][A object][enum.B][B object][enum.B][B object]...

Where after reading the message enum, we know how what message type to use for the next message.

If we use oneof, we should just be able to serialize the data as:

...[A object][B object][B object]...

While the memory size of oneof is the maximum of all variants, the oneof message needs only be initialized once: in the transmission thread. The objects sent to the transmission thread would be one of the submessages:

• Simulation thread creates a SimulationMessage, and sends it to the transmission thread via ChibiOS mail pool.
• Transmission thread clears the MasterMessage (oneof) and then sets the SimulationMessage field.
• Copy serialized data to tx buffer.

I imagine using enums we would avoid copying/moving the SimulationMessage into the MasterMessage but instead we would need to send out an EnumMessage on the wire in advance for every data type message.

[mickvangelderen]

we should just be able to serialize the data as:

...[A object][B object][B object]...

This data would be serialized as

[Master object][Master object][Master object]

which resolves into

[A tag][A object][B tag][B object][B tag][B object]

Because oneof declares multiple fields on the Master, each with their own id/tag/number. There is no magic. When you have multiple kinds of things, you need a way to tell them apart. If the field tags from the different types of messages in the oneof are unique, protobuf could determine the variant from that. The problem is they are not unique. Another problem is that the decoder would become more complex because you can not instantiate an object of the right type before you read the fields.

Sources:
https://developers.google.com/protocol-buffers/docs/proto3#oneof
https://developers.google.com/protocol-buffers/docs/encoding

[oliverlee]

I didn't think much about the receive side since that is happening on a desktop which isn't really memory constrained, however, we will face that problem for two way communication so thanks for bringing that up.

If the field tags from the different types of messages in the oneof are unique, protobuf could determine the variant from that. The problem is they are not unique.

I don't understand this point. Don't the field tags need to be unique in order for protobuf to correctly decode the message type? To me it looks like oneof is essentially equivalent to using enum except it's less work.

Another problem is that the decoder would become more complex because you can not instantiate an object of the right type before you read the fields.

This is a good point. The way I see it, there are two cases of messages (on microcontroller receive) we would handle and it may only be a problem for the second case. This assumes we have a txMasterMessage and a rxMasterMessage which are not equivalent.

1. Command case: Receive thread decodes the protobuf message into a rxMasterMessage which is allocated on the receive thread stack. The command is decoded and then a ChibiOS message (msg_t) is sent to the corresponding thread and that thread will then act when scheduled.
2. Data case: Receive thread decodes the protobuf message into a rxMasterMessage which is allocated on the receive thread stack. The data (and maybe an associated command) is decoded and then a ChibiOS mail pool is sent to the corresponding thread and that thread will then act when scheduled.

So in the data case, we'll also need to move the data out of the rxMasterMessage object to ... somewhere else. But the rxMasterMessage object is essentially a union, so I'm not seeing the problem. Unless, you were thinking about allocating memory for rxMasterSubmessageA directly from the memory pool and skipping the submessage copy?

I also don't think we should be concerned (as much) of inefficiency on the desktop side.

[oliverlee]

We're using the enum approach.

[oliverlee]

Asynchronous transmission is implemented in #197.
We can close this once we pre-transmit tags.