Part 7 of 14
Shared-memory transport
When the writer and the reader are separate processes on one machine, sending a sample through the network stack means copying it out of the writer, into the kernel, and back out into the reader. For large payloads, those memory transfers can be a significant part of the work.
The alternative is a region of memory mapped into both processes. The writer fills a slot and sends a descriptor identifying that slot, not a process address. A reader loan keeps the slot alive while the reader uses it. Eligible loan-based APIs avoid a full payload copy; value-based APIs may still serialize, deserialize, or copy the value.
What that buys in speed it pays for in difficulty. Several processes now access the same storage, so reservation, publication, and release must agree on ownership. The slot and notification mechanisms below use atomic state changes; crash cleanup is a separate responsibility.
This chapter describes native slot ownership and notifications, not RTPS packets carried through shared memory. Native notifications avoid RTPS wire framing and parsing, but still validate the segment, slot generation, payload size, and ownership. DDS history and admission policy still apply. When Security is enabled, the selected protection policy still applies too; sharing a machine is not authentication.
Allocation
Reserving a slot without a lock
a writer needs somewhere to put a payload
Once per published sample on the shared-memory path.
The region is divided into slots. A writer needs an unused one; when every reader has finished with it, it goes back. The unused slots are kept as a linked list — each free slot holds the position of the next one — with a shared variable naming the first. Taking a slot means reading that variable and moving it on to the next.
Between reading it and updating it, another process may have done the same thing. So the update is done with a compare-and-swap: a single machine instruction that writes a new value only if the variable still holds the value that was read. If it has changed, the write does not happen, and the whole thing is tried again from the new value.
Reserve-Slot(list)
list the free list, whose head is a pair: a slot and a counter that increases on every change
- loop
- h = Load(list.head) // h is a pair: a slot and a counter
- if h.slot == nil
- return empty
- s = h.slot
- next = s.next
- if s.state ≠ free
- h2 = Load(list.head)
- if h2 ≠ h
- continue // the list moved under us; the read was stale
- return corrupt // unchanged and still wrong: fail closed
- if Compare-And-Swap(list.head, h, (next, h.counter + 1))
- list.free-count = list.free-count − 1
- s.state = reserved
- return s
A slot on the free list that is not free
Finding a slot on the free list that does not look free has two possible explanations, and they call for opposite responses. Either the list changed while the slot was being examined — in which case the observation is simply out of date and the right move is to start again — or the list genuinely holds a slot that is in use, which means the shared region is damaged and continuing would hand a writer a slot somebody else is reading.
Re-reading the head separates them. If it changed, the first explanation holds. If it did not change and the slot still looks wrong, the second does, and the procedure refuses rather than guessing.
Allocation
The ABA problem
the reservation above attempts its compare-and-swap
Every reservation. The retry path runs only when two processes reserve at the same moment.
The head is not just a slot. It is a slot together with a counter that increases on every change. Without it the compare-and-swap is not enough, for a reason worth walking through slowly.
Compare-and-swap answers the question is this variable still what it was? What it is actually asked to answer is has anything happened since I read it? Those come apart when a value is removed and later put back. The variable reads the same, so the swap succeeds, but the world it described is gone. This is called the ABA problem: the value went A, then B, then A again, and the last read cannot tell that from never having changed.
The consequence in the middle row is the reason this matters. The swap
writes the stale next — slot B — as the new head of the free
list, while B has already been handed to another writer. Two processes
now believe they own it. One will overwrite the other's payload, and the
reader gets a sample that is half one message and half another.
The counter closes it. Every change to the head increments it, so the head after the sequence above is not the value that was read, even though its slot component is. The compare fails, and the retry works from what is actually there. Slot numbers repeat; the pair does not.
Cost
An uncontended reservation is O(1): one compare-and-swap, no allocation, no system call. Each time another process wins the race it adds one more O(1) attempt. There is no lock, so a process that is descheduled or killed mid-operation blocks nobody — it either completed its swap or it did not.
Notification
Notifying every reader of one payload
a payload has been written and readers must be told
Once per published sample, doing O(R) work for R local readers.
One payload usually has several readers, and each is told about it by having a small record — which slot, how big, which sample — appended to a queue it owns. Each queue has one writer and one reader and a fixed capacity.
When one queue is full
Appending to the first two queues and then finding the third full leaves two readers holding a reference to a payload whose publication is going to be abandoned. Undoing that means reaching into queues that their owners may already be reading.
So every queue is checked for room before anything is appended to any of them.
Notify-Readers(fanout, d, R)
fanout the writer's fixed array of reader queues · d the record naming the payload slot · R how many readers are configured, at most the array size
- for i = 1 to R
- c = Load(fanout.queue[i].consumer)
- if fanout.queue[i].producer − c == fanout.queue[i].capacity
- return unavailable // nothing has been appended
- for i = 1 to R
- Append(fanout.queue[i], d)
- Store(fanout.queue[i].producer, next position)
- Wake(fanout.queue[i].consumer)
- return ok
Checking and then acting is normally unsound in concurrent code, because the thing checked can change in between. Here it does not, and the reason is the shape of the queues rather than any lock. Each queue has exactly one process appending to it, and that is this writer, so no other producer can consume the space just observed. The only other participant is the reader, and everything it does frees space. A gap that exists in the first pass therefore still exists in the second.
Why the queues are separate
Each reader records how far it has got on its own queue, and the writer reads those positions separately. That is why the queues are separate rather than one shared queue: it makes one reader's progress unable to release a payload another reader is still using.
How a reader is notified
The queue itself works the same way on Linux and Windows: the writer publishes the next position and the reader observes it before reading the record. On Linux, a semaphore can put an idle reader to sleep until work arrives. On Windows, the runtime checks the positions from its owned service loop. The wake-up mechanism changes, but the fixed queue layout, ownership rule, and payload lifetime do not.
Cost
O(R) for R readers in both passes, with constant extra space. The queue array is sized when the writer is built, so notification allocates nothing. A failure to wake a reader after the record is written is not a capacity problem and is not treated as one — the record is there, and ordinary reliability repair covers it.
Attachment
Attaching to the shared region
a process joins the domain
Once per process at startup.
The region is created by a separate daemon and found by a name derived from the domain. A process attaching to it is about to treat those bytes as data structures, so what it must not do is take the region's own word for its shape.
The process does not use a size compiled into the client. Linux reports the region's logical size directly. Windows reports how much of the complete view is accessible, and the size recorded by the daemon is accepted only when it fits inside that view. A stale client or damaged header therefore cannot put reads outside the mapping.
A daemon that restarted
The daemon can restart and replace the region under the same name. Each generation carries a number, and the attaching process takes it from the mapping rather than from its own configuration — an application cannot ask for a generation, only discover the one that is there.
Attach(name, expected-id, needs)
name derived from the domain · expected-id the configured region identity · needs the pools this client requires to be usable
- m = Open(name)
- accessible = Accessible-Extent(m) // supplied by the operating system
- extent = Logical-Extent(m, accessible) // must fit inside accessible
- if not Valid-Abi(m) or not Valid-Layout(m, extent)
- return error
- (id, generation) = Read-Identity(m)
- if id ≠ expected-id or generation == 0
- return error
- if m.heartbeat == 0 or Capacity(m) < needs
- return error // a region that cannot serve this client
- return Attachment(m, id, generation)
Line 4 validates the whole shape before anything is read through it: the format marker and version, every size class in order, and that each metadata and payload range lies inside the mapping with the alignment the atomic operations require. Line 9 rejects a region whose daemon has never recorded a heartbeat, which is what an uninitialized mapping looks like.
Two processes creating it at once
Two processes may both find it missing and try to create it. The one that loses opens what the winner made — but may arrive while the winner is still filling in the header, and see it all zero. An all-zero header is treated as initialization in progress and retried briefly; a header that is non-zero but malformed is rejected at once. The distinction is between not yet written and written wrongly.
Reclaim
Reclaiming an abandoned slot
the daemon sweeps, using the set of participants discovery has declared gone
Once per daemon tick, reclaiming at most a configured number of slots per pass.
A process can be killed at any point, including while it holds a slot. Nothing will return that slot, so without a way to reclaim it the region leaks until it is empty.
Reclaiming is dangerous in the obvious way: a slot that looks abandoned but is still being read by a live process must not be given to a writer. So each slot records who has it — the writer that published it, and each reader holding a reference — in a small fixed table in the slot's own header.
Discovery already knows which participants have stopped announcing themselves. The daemon takes that set of departed owners and reclaims a slot only when everything about it can be accounted for.
Reclaim(slot, departed)
slot one slot being considered · departed the owners discovery has declared gone
- if slot.state == reserved and slot.refs == 0
- return Release(slot) // taken but never published
- if slot.state ≠ published
- return keep
- if slot.writer not in departed
- return keep
- n = 0
- for each owner o in slot.owners
- if o ≠ nil
- if o not in departed
- return keep // somebody live still holds it
- n = n + 1
- if slot.refs ≠ n
- return keep // a reference nobody claims: do not touch it
- return Release(slot)
Worked example
A slot is published by writer W and was handed to readers R1, R2, and R3. Discovery reports that W, R1, and R2 have gone.
| Case | Owners recorded | Count | Result |
|---|---|---|---|
| R3 still running | W, R1, R2, R3 | 4 | keep — R3 is not in the departed set |
| R3 has now gone too | W, R1, R2, R3 | 4 | release — every owner departed and the count agrees |
| All departed, count is 5 | W, R1, R2, R3 | 5 | keep — one reference belongs to nobody named |
The third case is the one worth dwelling on. Four owners are named and all four have gone, so by the owner list the slot is free. But the count says five references exist. Something holds this slot that the owner table does not know about, and the slot stays put — the count is trusted over the list, because the list is the thing more likely to be incomplete.
A reference nobody claims
Line 13 is the safeguard that does not depend on the owner list being right. If the count of references disagrees with the number of owners that can be named, then something holds this slot that cannot be accounted for, and the slot is left alone. Leaking a slot is recoverable; handing out one that is in use is not.
References that outlive the slot
Releasing clears the owner records, zeroes the count, and increments the slot's generation before returning it to the free list. That last part matters because a reference to the slot may still exist somewhere — in a queue, in a message in flight. Those references carry the generation they were made under, so once it has moved on they can be recognised as stale and refused, rather than resolving to whatever now occupies the slot.
Cost
The owner table is a fixed size — 16 records per slot — so adding, removing, or checking an owner is O(K) over a constant, not over the number of participants or readers in the system. Working out which owners have departed is O(P + E) over participants and endpoints, done once per sweep. Each sweep reclaims at most a configured number of slots, so the work per pass is bounded however much there is to clean up.
Progress
Every notification finishes
the notification worker services a protected entry
Once per notification.
Everything else on this page is a safety property: a slot is not reused while somebody reads it, a queue is not written unless every queue has room, a reference is not released twice. All of them say what must not happen.
None of them says the worker ever finishes with an entry. A notification that has been posted, whose payload has been borrowed and is waiting to be authenticated, violates nothing by staying in that state forever. The descriptor reference it holds is legitimately held; the slot it names is legitimately not reclaimable. The region simply fills up and stops.
So there is a separate obligation: every posted notification reaches one of exactly two outcomes, and both of them release the descriptor.
Service-Notification(n)
n one posted notification — its channel header, descriptor, and protected payload
- if not Valid(n.header) or not Valid(n.descriptor)
- return Reject-And-Release(n)
- bytes = Borrow(n.descriptor)
- if not Authenticates(bytes)
- return Reject-And-Release(n)
- return Deliver-And-Release(n)
There is no path out of this procedure that does not release. Both rejection branches and the delivery branch release, and there is no fourth branch — no "leave it for later", no early return that skips the release. That shape is what makes the argument straightforward: the number of outstanding notifications strictly decreases whenever the worker runs, so as long as it keeps running, the set empties.
The claim is deliberately weak, in the same way as the one in Part 12. It does not say the payload authenticates, or that the reader wanted it. It says the machinery cannot hold a descriptor forever without deciding about it — which is the failure that no amount of checking the safety properties would have caught.
Next: identity and permissions
Announcements are just bytes. Peers prove who they are and agree what each of them may do.
These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.