A switch has a queue of packets heading to the same place: some posted writes, some read requests, some read completions. It may send them in any order the rules allow. The rules fit in a three-by-three table, and the table looks arbitrary until you see that every cell answers one of two questions: "would passing here let a consumer see stale data?" and "would not passing here risk a deadlock?"
Which kinds of transaction may overtake which, and why?
The obvious rule is strict order: nothing passes anything. It is correct for producer/consumer and it can deadlock. A read request waiting in a full queue blocks the posted writes behind it; if the read cannot complete until those same writes drain somewhere else, nothing moves. The opposite rule, anything may pass anything, cannot deadlock this way and breaks data-then-flag. The table is the set of exceptions that keeps both properties.
Producer/consumer correctness says: a later access must not pass an earlier posted write. A flag write must not overtake its data write; a read must not overtake writes it is meant to observe; read data returned must not overtake writes made before it.
Deadlock avoidance says: posted writes and completions must never be blocked by non-posted requests. Non-posted requests need a completion before they finish, so they can wait on resources; posted writes and completions finish when delivered, so they must always be able to drain.
Read the table as "may the row's transaction pass an earlier transaction of the column's type, in the same direction on the same path?"
Later ↓ / earlier → | Posted write | Non-posted request | Completion |
|---|---|---|---|
Posted write | No: a flag must not pass its data (producer/consumer). Relaxed Ordering may permit it. | Must be able to: otherwise a blocked request can block writes it depends on (deadlock) | Must be able to (deadlock) |
Non-posted request | No: a read must see earlier writes; a read-back flushes posted writes (producer/consumer) | May, either way | May, either way |
Completion | No: returned data must not overtake writes made before it (producer/consumer). Relaxed Ordering may permit it. | Must be able to (deadlock) | May, between different requests; the pieces of one split read stay in address order |
Posted cannot pass posted: data then flag (lesson 7.1).
Non-posted cannot pass posted: the read-back rule (lesson 5.7): a read from a device confirms earlier writes to it have landed.
Completion cannot pass posted: a device that writes data to memory and then returns a read completion (or a status) must not have the completion seen first.
Posted and completions must be able to pass non-posted: non-posted requests can be stuck waiting for resources (completion buffers, credits); if posted writes and completions queued behind them, the traffic that would free those resources could never move (Part 9).
Everything else is free, because no correctness or deadlock argument needs it, and freedom helps performance.
Protocol | Passing rules |
|---|---|
PCI Express | Exactly this structure. A read request or non-posted write must not pass an earlier posted write; a completion must not pass an earlier posted write; a posted write must not pass a posted write; posted writes and completions must be allowed to pass non-posted requests. Relaxed Ordering and ID-Based Ordering relax some cells (lesson 7.7). |
AXI | No posted/non-posted distinction; ordering is per ID, and deadlock avoidance comes from channel independence and dependency rules (lesson 5.6). |
A bridge (illustrative) kept a single FIFO for all traffic towards a host. A device read stalled at the head of the FIFO waiting for completion credits, while behind it sat posted writes, including the ones that would eventually let the host free those credits. The system deadlocked under heavy DMA. Separate queues per traffic type, with posted writes and completions allowed to bypass blocked requests, are not an optimisation: they are the deadlock rule of the table.
A device may write data to memory and then return a completion (or status) that tells software to look at it; the completion must not be seen before the data.
Non-posted requests can wait for resources (credits, completion space); if posted writes queued behind them could never drain, the traffic that frees those resources could be blocked too: a deadlock.
A passing table says which traffic type may overtake which, in one direction on one path.
"Must not pass" cells come from producer/consumer correctness; "must be able to pass" cells from deadlock avoidance.
Implement them with separate queues per type, and justify every cell with one of the two reasons.