single_threaded_executor uses moved reference

[thirtytwobits]

On line 109 the callback node object is linked into the local CAVL tree. On line 110 that same object is moved into an Any that is returned from the registerCallback. This means the executor is working with moved-from memory. Not sure why this works?

[thirtytwobits]

I can't help but think this shouldn't work. line 219 links addresses in stack memory into the AVL tree?

[serges147]

I understand your concerns but it all was done thoughtful and purpose. Please see move constructor/assignment of CAVL node, specifically its moveFrom(Node& other) which is called from both move constructor and move assignment. In short - CAVL node automatically corrects all pointers around it (its children and parent) when it is moved to different memory location. Thanks to this feature (see original PR at pavel-kirienko/cavl#14), now not only whole CAVL tree is move-able but also any of its nodes are moveable as well. This was essential and required feature to be able make other libcyphal entities (like executor callback, various presentation and application layer entities, etc) as dynamic memory free objects. Dynamic allocations are in use ONLY for shared entities (and for transmission pipelines of course).

BTW, following to your concern, please take a look also at examples posix_single_threaded_executor, namely at its AwaitableNode which is not only CAVL node (via inheritance from the CallbackNode) but also DoubleLinkedNode - participating in doubly-linked list, which has two pointers (prev_node and next_node). And yet such awaitable node still freely MOVE-able !!! - see its move constructor and how it's calling its base classes.

[pavel-kirienko]

Here's the guiding principle behind this design (I just posted the same quote in an adjacent issue):

[thirtytwobits]

This violates the Principle of Least Astonishment. C++ is supposed to be expressive in a way that makes the programmer's intent visible. In this case we end up with something that reads:

CETL_NODISCARD Callback::Any registerCallback(Callback::Function&& function) override
{
    CallbackNode new_cb_node{*this, std::move(function)}; //< create an automatic object on the stack.
    insertCallbackNode(new_cb_node); //< insert that object into a member data structure
    return {std::move(new_cb_node)}; //< move the object, we just inserted into the local data structure, out of this object.
}

even more Astonishing:

void insertCallbackNode(CallbackNode& callback_node)
{
    const auto next_exec_time = callback_node.nextExecTime();
    const std::tuple<CallbackNode*, bool> cb_node_existing = callback_nodes_.search(  //
        [next_exec_time](const CallbackNode& other_node) {                            // predicate
            //
            return other_node.compareByExecutionTime(next_exec_time);
        },
        [&callback_node]() { return &callback_node; });  // "factory"
    (void) cb_node_existing;
}

in the above code [&callback_node]() { return &callback_node; }); // "factory" clearly returns a pointer to a memory location in the current callstack. There's no indication whatsoever that this is safe and valid code. If CallbackNode was copyable and that line read [&callback_node]() { return callback_node; }); // "copy" it'd make sense (even more Astonishing is that this is not a "search" but is actually an "insert" operation but that's another issue to open against CAVL).

What's further Astonishing is if you try to customize this callback node (as I did). For example:

libcyphal::IExecutor::Callback::Any FreeRTOSQueueExecutor::registerCallbackWithMemo(
        libcyphal::IExecutor::Callback::Function&& function, libcyphal::IExecutor::Callback::MemoType memo) {
    CustomCallbackNode new_cb_node{*this, std::move(function), memo};
    insertCallbackNode(new_cb_node);
    return {std::move(new_cb_node)};
}

then I do this:

FreeRTOSQueueExecutor::SpinResult QueueExecutor::spinOnce() {
    ...
    while (auto* const callback_node_ptr = callback_nodes_.min()) {
        auto& callback_node = *callback_node_ptr;
        ...
         // The memo, passed into the CustomCallbackNode constructor, is always 0x00
        if (callback_node.getMemo() == 0x01) {
            callback_node.schedule(libcyphal::IExecutor::Callback::Schedule::Once{now()});
        }

    }
...

or, if I do what one should do with an Any object and in-place construct it (see #403):

template <typename... Args>
libcyphal::IExecutor::Callback::Any registerCallbackInternal(Args&&... args) {
    libcyphal::IExecutor::Callback::Any cavl_node_any{
            libcyphal::IExecutor::Callback::Any::in_place_type_t<CustomCallbackNode>{}, std::forward<Args>(args)...};
    CustomCallbackNode* cavl_node_actually = cetl::get_if<CustomCallbackNode>(&cavl_node_any);
    insertCallbackNode(cavl_node_actually);
    return cavl_node_any;
}

libcyphal::IExecutor::Callback::Any FreeRTOSQueueExecutor::registerCallbackWithMemo(
        libcyphal::IExecutor::Callback::Function&& function, libcyphal::IExecutor::Callback::MemoType memo) {
    return registerCallbackInternal(*this, std::move(function), memo);
}

now it does explode when run.

Finally, I may not be the smartest engineer on the planet but I have been writing C++ for over 20 years and I still can't figure out how the CAVL code is safe and correct.

[pavel-kirienko]

You do make a valid point that the solution is somewhat unconventional for C++. I think such a strong reliance on moving is more likely to be found in, say, Rust, where move-rich approaches are encouraged by its ownership model. The design you are looking at is an attempt to meet the high-level design goal mentioned earlier by applying foreign concepts not often found in C++ codebases.

Perhaps we should try and clean up the rough edges in this design before undoing it entirely in favor of the more conventional but less appealing pmr-based design?

[thirtytwobits]

How would we do this? Again, I'm still not clear how the pointer-to-stack-memory is okay in the CAVL search/insert operation. If I could understand what's going on in that method then I'd be able to comment on how we would make this less Astonishing.

[serges147]

0. tree is empty (only origin node exists inside the Tree object, let's say at address 0x2000)
1. new_cb_node on stack addr 0x1000 is created - its Node part contains nullptr-s.
2. callback_nodes_.search is called - 0x1000 address of new_cb_node is inserted into the tree

• origin node.child[0] points -> 0x1000
• new node.parent -> 0x2000

4. return {std::move(new_cb_node)}; statement...

a. calls Any constructor, let's say on stack address 0x1080; inside it (let's say @ 0x1090 starts buffer of the any where future node will live)

b. as part of the above ctor Node's move constructor is called , where this==0x1090 and other==0x1000. this move constructor corrects tree pointers:
- origin.child[0] changes to point -> 0x1090 (instead of previous 0x1000)
- this.parent = other.parent , namely -> 0x2000
- other.parent = nullptr;
- as a result there is NO 0x1000 address anymore at the tree!!!

c. destructor of Node@0x1000 is called - does nothing b/c its pointers are all nullptr - so called "not linked" node.

d. return to the caller of registerCallback

If later whole Any is moved even further (f.e. as a return result) then its move constructor will be called, which internally of course calls move constructor of whatever object currently lives inside its buffer (in our case it's our Node@1090). If we imagine the new address of Any is f.e. 0x3000, then node address inside the tree will be, again, automatically and smoothly fixed (from old 0x1090 -> new 0x3010)

[serges147]

I agree with what you said about "Principle of Least Astonishment" only partially.
Yes, when you need integrate into such low-level stuff as executor then I agree you have to little bit get used of how callbacks are implemented inside single_threaded_executor, and unfortunately do some pointer magic if you wish. BUT when you start working with actual main api of libcyphal (like actual cyphal node and its application) then you don't really need understand what is happening inside (f.e. CAVL staff is not exposed in any way). Also, I would like to stress on point that nobody requires to even use single_threaded_executor if you don't like it - main codebase operates with IExecutor interface only, and its Callback::Any provides flexibility to embed inside any implementation you would like. Maybe RTOS implementation should not be inherited from single_threaded_executor at all... although I still think it makes sense reuse it as much as possible.

[pavel-kirienko]

@thirtytwobits can we give your CustomCallbackNode a closer look?

[serges147]

@thirtytwobits @pavel-kirienko
I would like establish a practice that any (or at least most) issue we create for libcyphal is accompanied with minimal (as small as possible), buildable and runable demo project which demonstrates the problem/issue. It could be for example done as a fork (or a branch) with necessary changes (f.e. in existing demos or unit tests) to reproduce the issue.