The Rust library uavcan.rs is looking for a new maintainer

The UAVCAN implementation in Rust – we call it uavcan.rs – is looking for a new maintainer. Please post here if you’d like to take that role.

Thanks!

UPD 30.09.2020: still looking :mag:

I am interested in commercially using the UAVCAN Rust implementation, and we are open to the idea of taking over maintainership for this crate.

What is the current state, what are the gotchas, what is currently missing in the implementation, and who else currently has a stake in the matter?

Great :sunny:

What is the current state

It’s been abandoned for the last ~1.5 years. At this point, I suspect it could be easier to restart from scratch and possibly make the API closer in spirit to PyUAVCAN.

what are the gotchas, what is currently missing in the implementation

It is rather early-stage, I would say. It’s been envisioned to implement the support for different transport protocols which would probably require revamping a lot of the existing code unless it is redesigned from scratch. I mentioned PyUAVCAN as a sensible reference because it was designed specifically to support different transports.

who else currently has a stake in the matter

Nobody. To the best of my knowledge, this implementation is neither actively used nor developed by anyone.

You are welcome to join our dev call if you want to discuss this in real-time.

Sounds good, I’ll be there :+1:

1 Like

Here is the list of basic requirements for the Rust library which seems uncontroversial:

  • Compatibility with deeply embedded environments where the standard library is not available (no_std).

  • Compatibility with different transports and heterogeneous redundancy (like PyUAVCAN): UAVCAN/CAN, UAVCAN/UDP, UAVCAN/serial, etc.

  • Statically bounded time complexity and memory utilization, like Libcanard. An O(1) memory allocator may be needed.

  • No implicit background processing.

  • Automatic (de-)serialization. Technically, though, this is not part of the Rust library, but rather a part of Nunavut.

  • MIT/Apache license.

Hi, let me chip in here. I’m also associated with Lasse (@finwood ) and the Rust advocate in the team. I’m currently quite busy, however, as far as my perception goes the current state of the crate is well worth to be continued on. AFAICT:

No problem. I like the idea of shipping the definition of messages and the interfaces (traits in Rust) in no_std crates. I then propose the creation of another crate, which implements these traits in a std environment based on UDP/Socketcan. Whoever desires to use them on his/her no_std platform of choice may implement them as well, however I will not put effort into the implementation for no_std. We won’t need it most likely, and the ecosystem is not stable enough for doing this just for the thrill.

This should already be the case in the current implementation, but if it is not it will be straightforward.

I guess this should be easily possible (- the O(1) allocator). Due to a nifty issue in Rust we can not make the code free of allocations easily without relying on unstable yet (const generics are not stabilized, so we can not template array sizes). Regarding the allocator: How would I determine if the allocator is O(1)? How is that even possible given that the allocator interacts with an OS in a std environment? Please pardon me for my questions, my knowledge in this area certainly is expendable…

Well, what does that mean?

What does this mean? Doesn’t it contradict the former point?

Yes. The dual licensing of MIT+ASL2 is the default for the Rust ecosystem and I see absolutely no problem with that.

Cheers

Hey @wucke13

Do I understand correctly that the former crate would not contain any logic at all? I would say that 99% of the protocol logic is entirely platform-agnostic and it can be implemented in a no_std environment. I am concerned that if we push the implementation outside of the core crate we would be forced to re-implement the same logic virtually identically for std/no_std environments.

Applications that run on a general-purpose OS like GNU/Linux are, in general, unlikely to benefit much from O(1) memory manager because the OS itself does not provide deterministic services, so in that case, it’s optimal to just stick to the default memory manager shipped with the standard library.

An embedded real-time system, on the other hand, cares about the temporal properties of memory management routines. To ensure that the application behaves predictably, the memory allocation and deallocation routines shall execute in constant time. To achieve that, an embedded system would typically set up the library to use a custom O(1) allocator. There are different memory management algorithms that are O(1), notably the buddy block allocator, half-fit, and the more advanced two-level segregated fit (TLSF).

Besides the temporal properties, another critical aspect is the worst-case memory fragmentation. An embedded system designer shall ensure that the application will always be able to allocate the required amount of memory from the heap regardless of the preceding sequence of allocations and deallocations. To achieve that, worst-case fragmentation models are used.

Unlike conventional applications, memory management algorithms used in real-time systems are optimized to deliver the best worst-case results rather than best average-case performance. As such, half-fit and the buddy allocator show higher fragmentation and their (de-)allocation requests require more computation on average, but their worst case on both metrics is significantly better compared to general-purpose algorithms. TLSF is different here – while being constant-complexity, its worst-case fragmentation is worse than that of the other two options which makes it a poor fit for highly deterministic systems.

If you want to learn more about the topic, you can find useful references in the docs for the allocator I wrote recently. It’s just about 500 lines in C so I suppose rewriting that into Rust would be a no-brainer. Here:

The Rust UAVCAN implementation should allow the user to provide a custom allocator, otherwise, it might end up being ill-suited for real-time systems. The allocator also should not panic on OOM, allowing the caller to handle the out-of-memory condition manually. I know that there has been some work underway to make standard Rust containers support best-effort memory allocation, although I don’t think it’s relevant for this library in particular: 2116-alloc-me-maybe - The Rust RFC Book. I don’t think it’s relevant because container resizing (and realloc() in general) is a linear variable-complexity operation which in general would make it inadmissible for a real-time protocol stack.

Our earlier libraries (libuavcan v0, libcanard v0) had certain internal routines dedicated to internal state maintenance, like discarding timed out transfer states and so on. This is undesirable for a real-time system because the temporal requirements of such activities are hard to account for. Our next-generation libraries (libcanard v1, pyuavcan v1 – although the latter is certainly not related to real-time) are purely reactive: they execute code only when a transfer is being emitted or a received frame is being processed. Additionally, in the case of libcanard, which should also be the case for uavcan.rs, the complexity of both is well-characterized, allowing the developer to make sensible architectural choices being assured of the temporal characteristics of the resulting system.

It means that we need to make Nunavut generate the serialization/deserialization code for uavcan.rs. Kjetil, the original author of uavcan.rs, intended to write a dedicated DSDL parser and code generator in Rust, but I’m not sure if it’s a sensible plan because this work is time-consuming and the time is better spent working on the core implementation. We already have a multi-language code generator Nunavut written by Scott so I suggest we rely on that.

1 Like

First of: Thank you for taking the time to educate me, TDIL :slight_smile:

I try to start by using numbers instead of block qoutes, so there we go:

  1. There is no unified IO scheme through std/no_std. In std there is the excellent Read/Write trait. So the actual implementation for sending and receiving through an interface will have to be different, depending on whether we have one specific CAN DMA interface, the smoltcp IP stack and for std both std::net, socketcan as well as async variants of these too. Probably there is still some lack of knowledge from my side, so; Is there protocol logic which can be implemented only on broadly abstracted hardware interfaces?

  2. So, this is not an issue for std, which is good. For no_std, Rust comes without an allocator. On a quick glances I did not see an allocator for no_std which explicitly claims to be O(1). As long as we do not need vectors, we might very well end up without having an allocator at all. This might workout nicely, and will very much contribute to a small footprint. If, then we are going to need an allocator to circumvent the restrictions about arrays (the size is part of the type + no const generics render them quite useless). In this case tinyvec might serve us well.

Oh no :laughing:, rewriting C code is almost never a no brainer since most concepts are not sound for safe Rust. Let’s see whether this becomes necessary.

  1. So you would opt for a polling based system, where the user has to call a step function periodically to keep things going? This sounds fine for me (but I have to research more about the libraries duties other than serializing and deserializing :smile:)

Am I understanding correctly that not having to use an Allocator at all for no_std would make use very happy, and having whatever comes as default for ordinary OSes is fine?

  1. This certainly would be nice (less useless, redundant code to maintain for me). We can either directly generate the Rust code from Nunavut, or we could use a build.rs script in a Rust Crate to generate the code on the fly using nunavut. However, the former seems to be the nice idea.

So far: Thank you for the conversation. Let’s that this might lead somewhere.

Edit: There is the buddy_system_allocator, so I guess the Allocator question is answered in any case.

1 Architecture

Yeah. Here is the layering model we use, as reflected in PyUAVCAN. It is not mentioned in the specification because the specification is only concerned about interoperability and behavioral guarantees, so, strictly speaking, this model is safe to disregard if it is found unsuitable, but it worked well for us so far:

  • Application – the user logic along with some high-level protocol features like plug-and-play nodes. I think Rust developers like their ecosystem highly modular so it might make sense to extract such optional high-level functions into a separate crate, but I could be wrong here.

  • Presentation – the core protocol abstractions (implemented as generics parametrized over the DSDL type): publisher, subscriber, client, and server. This logic is fully trasport-agnostic and is built on top of highly generalized Transport traits (similar to pyuavcan.transport.Transport).

  • Transport – individual transport layer implementations. For example, UAVCAN/CAN, UAVCAN/serial. Some of the transports may share common logic – for example, the framing logic in UDP and serial is virtually equivalent (see pyuavcan.transport.commons).

  • Media layer – the low-level transport-specific media access logic. For example, UDP over Berkeley sockets, CAN FD over SocketCAN, low-level drivers for chips and MCU peripherals, etc. This part is platform-dependent.

I imagine that the top three layers are invariant over the availability of the standard library. The media layer is where the differences start to become important because it actually bridges the protocol logic with the underlying communication hardware.

2 Memory management

I’m not sure vectors are relevant here. An allocator is likely to be needed for storing the RX transfer states; managing that using only static memory would be hard. Maybe you could have a quick glance at Libcanard and see if the memory management approaches used there make sense? I think @scottdixon was also planning to adopt similar strategies for Libuavcan v1.

True, but then again, I suppose you can’t implement dynamic memory management within the safe subset of the language – any allocator is inherently unsafe.

I had a quick look at the buddy allocator you linked and I think that it could be done better. The half-fit strategy is only marginally more complex compared to the buddy system and it may offer a better worst-case bound, especially on systems that leverage memory caches (this is covered in Herter’s thesis linked from O1Heap docs). Although I am drifting off-topic here. The key thing is that we should allow the library to be used with different allocators, everything else is probably irrelevant for now.

3 Control flow

We discussed it with Kjetil years ago, please have a glance:

I would recommend to stick to the Libcanard way of handling things, where the application feeds received data frames (like CAN frames, UDP frames, serial bytes, etc.) into the library, prompting it to perform parsing and demultiplexing internally, then delivering callbacks to the application as necessary. If there is no data to handle, the library should have nothing to do (excepting some high-level protocol features that may have its own state, but as I suggested above they may be kept reasonably isolated from the core library).

This is just my high-level view. It might turn out to be deficient upon a closer look.

4 DSDL transpiler

The new party policy is to keep all generation logic inside Nunavut. It is to become a multitool that can turn your DSDLs into Python, C, C++, and, well, Rust. It’s also going to emit support code together with the generated code, in case you want to use auto-generated structures with custom protocol implementation. See https://github.com/UAVCAN/nunavut/issues/102.

1 Like

There is https://github.com/japaric/tlsf which is certainly worth a look.

1 Like

Thank you for the heads up, I’m definitely a fan of Jorge’s work!

So far a few central question arose on my side:

Rust features powerful ways of code generation, like macros. These allow arbitrary manipulation of selected chunks of the token stream. One way of using these would be: A derive annotation on a struct automatically generates the serialize/deserialize code for said struct. TL;DR Rust offers a lot of in-house possibilities for code generation. Do we want to utilize this, or would we prefer having Nunavut generating a stand alone, fully featured crate for a given set of dsdl?

And as follow up: How should a user be able to integrate custom messages? As far as I understand the public regulated types are shipped already. Do we want nunavut to be able to create standalone crates for given dsdl sets? Is this even possible, or does the whole code generated from nunavut has to originate from one coherent invocation of nunavut, for example to prevent collisions in message ids?

I don’t think so.
If I read correctly, the Presentation requires us for example to remember, to which the node is currently subscribed. This is state, and the size of this state is not static. Therefore we need heap memory to store this state. If we need heap, we need to distinguish between std and no_std (plus additional complication if the user shall be able to choose the allocator for no_std). We certainly can circumvent this, if we delegate the effort of homing all non statically sized things to the user (and having him give us a &mut to our state all the time). However, especially on non-embedded devices this makes up a terrible API.

In general, Rust not only provides tempting safety features, but also very nice API modelling capabilities. However, the latter is somewhat limited on no_std. I would like to have the API as nice as possible, so some additional things for std (e.g. internal handling of subscriptions).

So far my perception goes into this direction:

A no_std uavcan crate, let’s call it uavcan-core with the following elements with some types and traits, but very sparse implementation. Basically only the needed transformations, from presentation to transport and vice versa.

A std uavcan crate with fully featured logic, including plug-and-play nodes and drivers for udp and socketcan (as opt-out feature, to allow for uavcan/udp only code to run on windows/mac as well).

What do you think, @pavel.kirienko ?

The point of using Nunavut is to avoid doing the same thing twice, like DSDL AST transformation. If we were converting DSDL into Rust using Rust macros instead of Nunavut, then what you are describing would be an option, but if we are using Nunavut to generate structs, then we should use it to generate (de-)serialization logic as well because the rules of such code generation are occasionally sophisticated unless you don’t care about the performance and CPU overhead.

Yes. We call such DSDL sets namespaces. It is perfectly legal to just generate some code from an arbitrary namespace on a whim.

A Rust crate is a sensible representation of a DSDL namespace. Likewise, in PyUAVCAN, we convert DSDL namespaces into Python packages.

Let’s align on the goals. UAVCAN is a real-time protocol for high-integrity applications and Rust is a systems language well-suited for programming complex and robust embedded systems. I derive from that that uavcan.rs should treat embedded systems as the first-class applications. Ergo, given our limited resources, no_std is the primary environment, std comes after. I think it might be tempting to say that we want both but if that were not an option, would you agree?

Applications that require highly deterministic behaviors should minimize their reliance on the facilities whose characteristics are harder to analyze, such as heap memory (even if it’s constant-complexity). Hence, if it is possible to avoid dynamic memory allocation (or some other undesirable activity) without harming the generality and reusability, it should be avoided. In the case of the Presentation layer specifically, I imagine that it is going to be possible to avoid any dynamic memory allocation cheaply by keeping state in non-clonable handle objects (such as Publisher/Subscriber/Client/Server in PyUAVCAN or Libuavcan v0).

(N.B.: speaking about heap memory specifically, keep in mind that to allocate X bytes statically you only need to reserve X bytes, whereas to guarantee that the same X bytes can be allocated from the heap at all times you need to reserve M×X bytes where M>>2 due to fragmentation.)

It is easy to avoid dynamic memory everywhere except the transport layer due to the fact that the resource utilization of the transfer reassembly logic is heavily dependent on the state of the network, which is hard to predict when developing reusable software. As a software service, dynamic storage management is easy to abstract away without compromising on type/memory safety and API design, too. Would you agree?

Could you please elaborate on what are the API features that you find desirable that are unavailable in no_std? Also, I am not sure what do you mean by “internal handling of subscriptions”.

I doubt it’s going to work as you expect it to. API aside, the protocol implementation is cheap to implement in no_std, the same should be true for PnP and other application-layer features. May I suggest instead to consider implementing everything in no_std with an optional std-enhanced API facade on top of it published in a separate crate?

Regarding the "would you agree"s :slightly_smiling_face: :

  • Not using anything from the Rust ecosystem for the Rust code generation: Whatever floats your goat. I’m fine with doing it fully based on Nunavut.
  • Having Nunavut create standalone crates for namespaces: Sure!
  • Aligning Goals: I understand, you want no_std first. This is not matching up with @finwood’s/my use case, but it’s not directly conflicting it. I’m by far more experienced in the std zone, which is the primary reason why I prefer using it. I don’t have a good feeling for what makes up a nice no_std API yet.
  • Avoiding dynamic memory everywhere (except transport): From my current knowledge, this is impossible for me. However, I’ll investigate the options of the Rust ecosystem, so far our conversation unveiled quite a bit of misconceptions on my side already! That’s why I cant agree so far. I don’t know of another way of storing an arbitrary number of things other than a fixed size array on stack (if heap is not allowed).
  • API features from std, that are nice: std::net::UdpSocket, std::io::{Error, Read, Write} are the ones I meant. For example, we could implement the serializing/deserializing of the actual payload just on Read/Write traits. For no_std, we would probably going for &mut [u8] then. The more I think about this though, the more issues with this thought I can see. For example UdpSocket doesn’t even implement Read/Write as UDP is not stream oriented…
  • “internal handling of subscriptions”: If I understood correctly, a node can subscribe to certain subjects. Ideally, I would like to have a struct which represents the state of a node (hence “internal handling of subscriptions”, as the struct representing the nodes current state internally stores said state). However, this is not possible without heap, as there is no way of knowing the size of the state as we do not know the number of subscriptions to be active (of course we could just allow for up to n subscriptions, but that is terrible IMHO). I hope this clears it up?
  • I think what I mean with “very sparse implementation” is the same what you mean with “everything”, just that there is for sure some trivial functionality that I’m not aware of yet. From that standpoint, I guess what you propose is equal to my initial thought, hence: Yes, you may suggest :smile:!

I guess I got a lot of homework to do. So far thank you for the input, I hope it accelerates the process on my end.

1 Like

Yeah. Indeed, without heap we may be unable to keep the state compact, requiring separate per-session states. I think it’s fine though and it seems to map onto the protocol logic nicely.

Hi @wucke13! It’s been almost three weeks already; do you need help/advise from our side to help you move forward?

Hi @pavel.kirienko, thank you for the heads up! I’ve started by translating canard to Rust. On doing so, I desired to use uX, a lib that kjetil once wrote to cover custom width integer types. However, uX is in a bad shape, as it does not allow for Try{From,Into} conversions (e.g. trying to cast an i17 to an i9). So, currently I’m working on an alternative. The process is much more tedious than thought due to

I hope that I will be able to finish this work on the custom width integers in the next weeks, but up till now the semester is also calling for my time. I have some good news though: It looks like I’m going to be able to connect the Rust implementation of UAVCAN with my research at university. If this works out, I’m going to be able to work close to full time on it for a couple of months.

Do you have any sweet idea about what to do with the custom width integers?

1 Like

Maybe consider using the standard-width integers only, as we do in C++/C? I realize that this approach loses the expressivity of DSDL somewhat, though.

Ok, let’s play this through. If we use only the standard width types:

  • What do we do if at least one out-of-bounds bit is set on a message to be transmitted?
    • Do we silently ignore it (for example using a bitmask with &&)?
    • Do we return an error?
    • Do we panic?
  • If transmitted (after serialization), is a u11 always exactly eleven bits wide (thus resulting in arbitrary bit length messages), will each field be padded to the next byte, or will the whole message be padded to a one byte alignment? (I shortly looked into the spec and did not find it, if you just name a sub chapter that would be lovely)

This is covered in section 3.4.2.2 Cast mode.

Section 3.7.3 Primitive types.

1 Like