MESI State Transitions

This chapter defines the coherence state machine of a requester (core-side cache controller). States describe a single cache line in a single core’s private cache.

State definitions

State	Valid?	Dirty?	Other copies?	Description
M (Modified)	Yes	Yes	None	The only valid copy in the system; memory is stale. The core may read and write freely. The line must be written back before being relinquished.
E (Exclusive)	Yes	No	None	Sole cached copy; memory is up to date. The core may read freely and may write via the silent transition E → M without notifying the CM.
S (Shared)	Yes	No	Possible	Clean copy that other cores may also hold; memory is up to date. Reads hit; writes require an Upgrade.
I (Invalid)	No	—	—	No valid copy present. Any access misses and generates a request.

System-wide invariants

Rule	Requirement
PL-MESI-01 (single-writer)	At most one core holds a given line in E or M at any time, and when it does, no other core holds the line in any valid state.
PL-MESI-02 (clean-shared)	When any core holds a line in S, memory holds the current data for that line.
PL-MESI-03 (dirty-uniqueness)	Dirty data for a line exists in at most one place: a single M copy, or a single in-flight WriteBack payload, never both and never more than one of either.

Transition table

Events are of three kinds: processor accesses (CPU Read, CPU Write), capacity Eviction, and received B-channel messages. Response messages the core must emit are listed as actions.

State	Event	Action	Next state
I	CPU Read	Send ReadShared; stall until grant	S on GrantS; E on GrantE
I	CPU Write	Send ReadExclusive; stall until grant	E on GrantE, then silent E → M when the write performs
I	Invalidate	Send InvAck	I (see rule PL-MESI-06)
S	CPU Read	Hit; no message	S
S	CPU Write	Send Upgrade; stall until GrantM or Nack	M on GrantM; on Nack, retry as ReadExclusive from I (rule PL-RACE-03)
S	Eviction	Silent drop; no message	I
S	Invalidate	Send InvAck; drop line	I
E	CPU Read	Hit; no message	E
E	CPU Write	Silent transition; no message	M
E	Eviction	Silent drop; no message	I
E	Invalidate	Send InvAck; drop line	I
M	CPU Read / CPU Write	Hit; no message	M
M	Eviction	Send WriteBack (dirty data); await WriteBackAck	I
M	Invalidate	Send WriteBack (dirty data) — the implicit InvAck; await WriteBackAck	I

Requester rules

Rule	Requirement
PL-MESI-04	Silent transitions. Exactly three state changes occur without any message: E → M on a store, S → I on eviction, and E → I on eviction. All other transitions are message-driven.
PL-MESI-05	A core shall issue Upgrade only from S, and shall issue WriteBack only for a line it holds in M (or held in M when the triggering Invalidate arrived).
PL-MESI-06	A core shall respond to Invalidate in every state, including I. An Invalidate can legitimately arrive for a line the core no longer holds, because clean evictions are silent (PL-MESI-04) and a voluntary WriteBack may be in flight: the CM’s directory can over-approximate the true set of holders. In all such cases the correct response is InvAck.
PL-MESI-07	A core shall not cache or use granted data before the grant transfer completes, and after transitioning to I shall not use stale data from the relinquished line.

Note

Transient states. This specification defines only the four stable states. Real controllers implement transient states while a request is outstanding (e.g. I-awaiting-grant, S-awaiting-GrantM). PicoLink does not standardize their encodings; it constrains only the externally visible message behavior. The race rules in Ordering, Races, and Atomicity define the required behavior when a B-channel message arrives while a request is outstanding - notably Invalidate arriving during a pending Upgrade (rule PL-RACE-03).

State diagram

        stateDiagram-v2
    direction LR
    I --> S : CPU Read / GrantS
    I --> E : CPU Read or Write / GrantE
    S --> M : CPU Write / Upgrade→GrantM
    E --> M : CPU Write (silent)
    S --> I : Eviction (silent) or Invalidate/InvAck
    E --> I : Eviction (silent) or Invalidate/InvAck
    M --> I : Eviction or Invalidate / WriteBack
    I --> I : Invalidate / InvAck