Ruby recycle and stall_and_wait message delivery errors

[JenniferBrana]

Describe the bug
A clear and concise description of what the bug is.

I am implementing cache coherence protocols using Ruby and have encountered issues with both the "recycle" and "stall_and_wait" functions that cause deadly protocol errors. I have attempted to use both recycle and stall_and_wait to deal with messages that cannot be currently processed by the coherence protocol (referred to as "deferred messages" below). I describe the individual issues below:

recycle: recycle moves the deferred request from the head of the queue to the tail to allow other messages to be processed immediately. I have encountered a case where this reordered deferred messages on the same message channel (for example, when there were two messages on the same network). When the receiving cache can later observe the deferred messages, the messages are observed out of order, causing the coherence protocol to believe the later message was sent before the earlier message. This causes a protocol deadlock in Ruby.

stall_and_wait: stall_and_wait moves the deferred request into a separate structure tagged by an address. I have found that if there coherence protocol attempts to defer multiple messages using stall_and_wait, the earlier message which was deferred is overwritten by later calls to stall_and_wait. This causes the earlier message to disappear entirely, causing obvious issues in the coherence protocol.

Affects version
State which version of gem5 this bug was found in. If on the develop branch state the Commit revision ID you are working.

Version 22.1.0.0

gem5 Modifications
If you have modified gem5 in some way please state, to the best of your ability, how it has been modified.

I have implemented a custom coherence protocol using Ruby.

To Reproduce
Steps to reproduce the behavior. Please assume starting from a clean repository:

Unfortunately, I am not sure how to reproduce these bugs without our coherence protocol. However, I believe it is inherent in the design of these mechanisms based on the source code that these errors could arise if multiple messages arrive on the same channel and are deferred.

Terminal Output
If applicable, add the terminal output here. If long, only include the relevant lines.
Please put the terminal output in code blocks. I.e.:

#Terminal output here#

Expected behavior
A clear and concise description of what you expected to happen.

Host Operating System
Ubuntu 22.04, Mac OS X, etc.

Host ISA
ARM, X86, RISC-V, etc.

Compiler used
State which compiler was used to compile gem5. Please include the compiler version.

Additional information
Add any other information which does not fit in the previous sections but may be of use in fixing this bug.

[powerjg]

Thanks for bringing this to the attention of the gem5 community! I think that most of the behavior you're seeing is expected (though there may be a bug if messages are overwritten in the stall queue). So, until we have more evidence of a bug (e.g., a reproducible error or some specific code that could be the culprit), I'm going to convert this to a discussion. I've included some further thoughts below.

recycle: recycle moves the deferred request from the head of the queue to the tail to allow other messages to be processed immediately. I have encountered a case where this reordered deferred messages on the same message channel (for example, when there were two messages on the same network). When the receiving cache can later observe the deferred messages, the messages are observed out of order, causing the coherence protocol to believe the later message was sent before the earlier message. This causes a protocol deadlock in Ruby.

This is expected behavior in Ruby. In fact, generally it is best practice that your protocol can deal with messages out of order. The default for the network is to also allow messages to appear out of order (e.g., what happens if a lower priority virtual channel is more congested than a higher priority virtual channel).

stall_and_wait: stall_and_wait moves the deferred request into a separate structure tagged by an address. I have found that if there coherence protocol attempts to defer multiple messages using stall_and_wait, the earlier message which was deferred is overwritten by later calls to stall_and_wait. This causes the earlier message to disappear entirely, causing obvious issues in the coherence protocol.

This could be a bug. As far as I know, when you use stall_and_wait all messages should be awoken when you call wakeUpAllBuffers. Now, there is some serious subtlety in wakeUpBuffers vs wakeUpAllBuffers, which I would have to dig into the implementation to see exactly how they work. If there are messages that are "lost", this would be both a bug in Ruby and a memory leak. If you could point to the code that you think isn't right, I could take a closer look.

That said, if you use stall_and_wait you'll still have the same reordering problem as recycle. I.e., there is no guarantee of ordering when messages are awoken in the stall queue or between new incoming messages being processed and messages in the stall queue.

[mattsinc]

@JenniferBrana : without know more about your protocol, it's hard to say, but the issue @powerjg mentioned above about wakeUpBuffers vs. wakeUpAllBuffers sounds like the root issue to me. We had several issues with this previously, and effectively for the public GPU protocols we removed all calls to wakeUpBuffers and converted them to wakeUpAllBuffers because of this very issue. You can see an example here: https://gem5-review.googlesource.com/c/public/gem5/+/31996, but there are several others with similar changes.

[JenniferBrana]

Thanks for the response. We have observed issues with messages disappearing when using stall_and_wait when using both wakeUpBuffers and wakeUpAllBuffers. Based on my limited knowledge of gem5, I believe the source of the issue is in mem/ruby/slicc_interface/AbstractController.cc in the "stallBuffer" function. I have observed this function overwrite currently stalled messages, causing the older message to disappear entirely. Our protocol is more complex than standard protocols which may be why we have encountered these issues. Currently, we are preparing for submission so I cannot provide the protocols at this time. We have resolved some of the issues by using alternative methods (i.e. replacing calls to stall_and_wait or recycle with empty actions or making the protocols stalling where necessary) but this has significantly increased development time.

[powerjg]

The code in question

void
AbstractController::stallBuffer(MessageBuffer* buf, Addr addr)
{
    if (m_waiting_buffers.count(addr) == 0) {
        MsgVecType* msgVec = new MsgVecType;
        msgVec->resize(m_in_ports, NULL);
        m_waiting_buffers[addr] = msgVec;
    }
    DPRINTF(RubyQueue, "stalling %s port %d addr %#x\n", buf, m_cur_in_port,
            addr);
    assert(m_in_ports > m_cur_in_port);
    (*(m_waiting_buffers[addr]))[m_cur_in_port] = buf;
}

I have to say, this code is incredibly confusing! Here's the best understanding I have.

m_waiting_buffers is a std::map<Addr, std::vector<MessageBuffer*>* > So, it's "just" a map from addresses to a set of buffer pointers we need to wake up. Thus, if the same address is stalled multiple times, the same buffer point will be awoken, which is the correct behavior. I do not believe this is a bug or a memory leak.

stallBuffer is called in stall_and_wait (in SLICC), and so is stallMessage. The code for stallMessage is shown below.

void
MessageBuffer::stallMessage(Addr addr, Tick current_time)
{
    DPRINTF(RubyQueue, "Stalling due to %#x\n", addr);
    assert(isReady(current_time));
    assert(getOffset(addr) == 0);
    MsgPtr message = m_prio_heap.front();

    // Since the message will just be moved to stall map, indicate that the
    // buffer should not decrement the m_buf_msgs statistic
    dequeue(current_time, false);

    //
    // Note: no event is scheduled to analyze the map at a later time.
    // Instead the controller is responsible to call reanalyzeMessages when
    // these addresses change state.
    //
    (m_stall_msg_map[addr]).push_back(message);
    m_stall_map_size++;
    m_stall_count++;
}

Here, each message is added to the m_stall_msg_map[addr] vector. So, I don't see that messages will be lost. It looks like they will all be in the list of stalled messages.

The messages go back onto their respective queues in reanalyzeList (via reanalyzeMessages or reanalyzeAllMessages). This puts the messages back in the message buffer. And, I was wrong before, this puts them on the message buffer in the original arrival order so if you have strict ordering in your network, you should have strict ordering when using stall_and_wait.

I suggest using the debug flag RubyQueue and grep for the address that you're having problems with. Given my experience with Ruby/SLICC writing many protocols (and spending weeks/months/years debugging protocols), I doubt this code has bugs if used in way it was intended. I've had many controller implementations which have race conditions on the same address and not run into this issue.

All that said, I have great sympathy for you trying to debug this! I said "if used in the way it was intended" above, and, I'll be honest, the only way to know that is to talk to the people who originally wrote the code over 13 years ago (looking at the git blame). I wish we had better documentation, but we only have so many resources, and documentation is not at the top of the list 😢.

[JenniferBrana]

Thank you for the advice, I'll give those methods a try!

[BobbyRBruce]

@JenniferBrana : Did you find out anything using @powerjg 's suggestion?