Session storage structure

[pavel-kirienko]

Context:

https://github.com/OpenCyphal-Garage/libudpard/blob/2e304642be8acbb8e66779cb86087896870f25fe/libudpard/udpard.h#L264-L265

It was discussed once somewhere, either on GitHub or on the forum, that the solution is to replace this array with another tree, thereby trading $O(1) \rightarrow O(\log n)$. It may be possible to join this tree with the higher-level one by extending its key. We can discuss this in-depth if necessary.

[SchoberMJ]

Agreed, we did talk about this on the forum or in one of the virtual meetings. Replacing it with an tree makes sense. We may want to think about the type of tree and data structure, but that should be doable.

For example, could we use another instance of an AVL tree?

[pavel-kirienko]

As discussed at the call, this array should be replaced with another AVL tree whose nodes are struct UdpardInternalRxSession:

https://github.com/OpenCyphal-Garage/libudpard/blob/2e304642be8acbb8e66779cb86087896870f25fe/libudpard/udpard.h#L277

And the definition of struct UdpardInternalRxSession itself needs to be extended with uint16_t remote_node_id; also, the first field would be UdpardTreeNode base;:

https://github.com/OpenCyphal-Garage/libudpard/blob/2e304642be8acbb8e66779cb86087896870f25fe/libudpard/udpard.c#L673-L683

[emrainey]

Something needs to change as this is eating 256KiB per single subscription on our platform which does not even have enough RAM to have even 2 of those.

[emrainey]

@pavel-kirienko Would the AVL tree per Node ID be fufilled through o1heap or would this be more statically limited?

[pavel-kirienko]

Something needs to change as this is eating 256KiB per single subscription on our platform which does not even have enough RAM to have even 2 of those.

Yeah, I understood that the current solution was known from the start to be a mere prototype. Maybe even libcanard needs to adopt this approach, at least as a build option.

Would the AVL tree per Node ID be fufilled through o1heap or would this be more statically limited?

It will come from o1heap and it will be statically limited, assuming that the number of nodes emitting matching transfers is limited. If something comes from the heap it doesn't make it automatically unpredictable.

[pavel-kirienko]

Note to self: the AVL key for the subscription state is (remote_node_id, redundant_transport_index)