This is the design of the ring buffer behind Starnix tracefs. Any number of threads append trace records to it without taking a lock, and a trace reader takes them a page at a time in the Linux ftrace page format. Use it to build an implementation, and to review one against it.
A ring buffer is a fixed-size FIFO whose slots form a circle. Writers add data at the tail, a reader removes the oldest data at the head, and both wrap around. When the buffer fills, it either rejects new data or overwrites the oldest.
In Starnix, writers are Linux programs writing to tracefs, and each write becomes one record. A trace consumer reads one buffer per CPU through per_cpu/cpuN/trace_pipe_raw and parses the pages as ftrace ring-buffer pages.
The Linux algorithm doesn't carry over, because it relies on how Linux writers behave. A Linux buffer belongs to one CPU, only code on that CPU writes to it, and writers nest: an interrupt that writes a record finishes before the code it interrupted continues.
Starnix writers are ordinary threads, and any thread's write can go to any buffer. The scheduler can pause a writer at any instruction for any length of time, while other writers fill the buffer and wrap it many times. Most of this design is about what a writer finds when it resumes.
The write and read paths take no lock, because a lock shared by all writers would let one paused writer stall the rest.
A paused writer can still delay the reader. A page becomes readable only once every writer that reserved space on it has committed, so until the paused writer resumes, the reader gets Nothing ready for that page and every page after it. Meanwhile the other writers keep filling the ring. Once it wraps onto the paused writer's page, they fail with Full (overwrite off) or drop their records (overwrite on).
Any number of writers append records at once, and one reader at a time takes finished pages. A controller creates the buffer with a capacity and an overflow policy, and enables and disables it. Its calls are rare and take a lock that writers and the reader never touch. Disabling discards the contents and frees the memory; enabling starts again from empty.
A writer reserves space for a record of a given size, writes the record into that space, and commits it. Between reserve and commit, the space belongs only to that writer, so it can write the record in place without a lock while other writers reserve their own space.
The reader asks for one page and gets a copy of the oldest finished page, or an answer that none is ready.
| Operation | Outcomes |
|---|---|
| reserve | Reserved, with the record's time delta; Full (no space, |
| overwrite off); Dropped (overwrite on, but the record can't be | |
| placed without waiting); Disabled; Invalid size. | |
| commit | Always succeeds. |
| read | A page; Nothing ready; Disabled; Busy (another read is running); |
| Buffer too small. | |
| enable | Enabled (no change if already enabled); Out of memory, leaving |
| the buffer disabled. | |
| disable | Disabled, with the counts of lost records and lost pages. |
A record must fit in one page's record area. A writer must commit every reservation promptly and with a complete record, because disabling the buffer waits for every outstanding reservation.
The buffer holds a fixed number of pages, each the system page size, in the ftrace layout, little-endian:
bytes 0..8 timestamp time of the first record on the page, in ns
bytes 8..16 commit low bits: number of record bytes that follow
bit 31: records were lost before this page
bytes 16.. records packed records, then unused space
A consumer parses commit bytes of records after the header and ignores the rest of the page.
Each record starts with a 32-bit header holding a 5-bit type-or-length field and a 27-bit time delta, the time since the previous record on the page. The first field, type_len, selects the record type:
type_len | Type | Meaning |
|---|---|---|
| 1 to 28 | Data | Payload of type_len * 4 bytes. |
| 0 | Data | Payload length in the first u32 of the payload, |
| for payloads over 112 bytes. | ||
| 29 | Padding | Skipped by consumers. With time_delta 0, it |
| fills the rest of the page; otherwise its | ||
| length is in the next u32. | ||
| 30 | TIME_EXTEND | The next u32 holds bits 27 to 58 of the delta |
| to the following record. | ||
| 31 | TIME_STAMP | An absolute time: time_delta holds bits 0 to |
| 26 and the next u32 holds bits 27 to 58. |
The caller writes data records, with the time delta the buffer gives it. The buffer writes a time-extend record in front of any record whose delta doesn‘t fit in 27 bits, about 134 ms. It never writes padding or time-stamp records: the space after the last record lies outside commit, and a page’s first record takes its absolute time from the page header.
When every page holds unread data, a buffer created with overwrite on lets a writer that needs space discard the oldest finished page, and counts it as a lost page. With overwrite off, that writer fails with Full and the old data stays. Capacity is fixed between enable and disable.
The pages sit in a fixed circular order. A page holds only the ftrace header and records, because consumers parse its bytes directly. The buffer keeps the state in its own metadata memory, outside the page data:
| State | Contents |
|---|---|
| tail word | Index of the page writers append to, and a |
| generation that increases on every move. | |
| head word | Index of the oldest page, a generation, and an |
| owner bit held by the thread consuming the head. | |
| claim word | Offset of the next free byte, a closed bit, and |
| (per page) | the low bits of the last claimed record's time. |
| writer state | An open bit and the number of active writers on |
| (per page) | the page. |
| ring word | An enabled bit and the number of reservations |
| and reads in progress. A reservation is in | |
| progress until it is committed. | |
| last time | The latest record time handed out. |
| lost flag | Set when records or pages were lost since the |
| last read. | |
| reader flag | Set while a read is running. |
The pages from the head up to the tail hold data, and the pages after the tail and before the head are reset and free. The buffer is full when the page after the tail is the head, and nothing is finished when the head is the tail.
Resetting a page sets its claim word to the start of the record area, open, with no time, and then sets its writer state to open with no active writers.
Integrity:
commit field equals the bytes of the records on it, packed from the start of the record area.commit range of a later use.Delivery and loss:
Time:
Lifecycle:
Progress:
Several writers reserve space on the same page at once, and each needs its own range. A writer reads the page‘s claim word, works out the record’s time and the length it needs (see Stamping records), and checks that the page is open and the record fits. It then compare-and-swaps (CAS) the claim word from the value it read to the new offset and time. If another writer got there first, the CAS fails and the writer starts over from the value it returned. A failed claim takes no space, and the offset never passes the end of the page.
Writers finish in any order. A slow writer can still be copying its record into a page after faster writers have filled it and moved several pages on. So the claimed offset doesn't tell the reader that a page is done.
Instead, each page counts its active writers. A writer joins the page (increments the count) before it claims space, and leaves it (decrements the count) with release ordering after it writes its record. The reader takes a page only when an acquire read of its writer state shows the page closed with no active writers. Every change to the writer state is a read-modify-write, so the value the reader sees is in the release sequence of every writer‘s decrement, and every record write happens before the reader’s copy.
The page‘s size has to be fixed when it closes, while other writers may be claiming space on it at that moment. The writer whose record doesn’t fit closes the page before it leaves it. It sets the closed bit in the claim word with an atomic OR, which also returns the final offset. Claims before the OR are inside that offset, and claims after it see the closed bit and fail.
Only one writer writes a page's commit field: the one whose OR found the closed bit clear. The OR is a single atomic step, so when several writers close the page at once, exactly one sees the bit clear. The others see it set and do nothing more. The closing writer writes commit and then clears the open bit in the writer state with release ordering. That stops new writers from joining and makes commit visible to the reader along with the records. Writers that claimed space before the close may still be writing, which is why the reader also waits for the active-writer count to reach zero.
The reader copies the head page out while the page stays in the ring, rather than swapping it out as Linux does (see Design tradeoffs). It takes the head by setting the owner bit in the head word with a CAS, then checks that the page is complete and isn‘t the tail. It copies the page into the caller’s buffer, resets the page, and stores the head word with the next index, the next generation, and the owner bit clear, with release ordering. While the reader owns the head, no writer can discard that page or move the tail onto it.
A reused page must not be touched by writers from its earlier use, and writers in its new use must not see the old closed state. The first holds because the page is reset only after its active writers have left. The second holds because the reset ends with a release store that opens the writer state, and a writer joins with an acquire read-modify-write on that state, so it sees the reset claim word. A writer moving the tail onto a free page has also acquired the head word, which was stored after that page's reset.
A reader or writer that reads shared state, is paused, and resumes after the ring has wrapped can find a page that looks the same but now belongs to a newer use. If it acts on what it remembers, it can write into, close, or discard that page.
The head and tail words carry generations, and every update to them is a CAS from the exact value the thread read, so a stale update fails. Each index shares a 64-bit word with its generation. With at most 2^20 pages, the generation gets 43 bits, which take about 97 days to wrap at a million moves a second.
Pages are protected by their active-writer count. A writer joins the tail page and then reads the tail word again; if it changed, the writer leaves and starts over. A page with active writers is never reset, so a writer that passes this check claims space on, and closes, only the page it meant to. A writer that can't join the tail page because it is closed, or whose claim fails because the page is closed, moves the tail and starts over.
The reader moves the head when it takes a page. With overwrite on, a writer that needs space also moves it, by discarding the oldest page. Only the holder of the owner bit may move the head, so a page is never both delivered and discarded.
A writer decides the buffer is full only if the tail word is unchanged after it reads the head word. Every tail move changes the generation, so the tail did not move between the two reads, and the head and tail it saw were current together when it read the head.
An overwriting writer takes the owner bit with an acquire CAS from the exact head word it read. It then checks that the head page is complete and that the tail word still holds the value that showed the buffer full. If the page still has active writers, the overwriter restores the head word, drops its own record, counts it, and sets the lost flag. If the tail moved, it restores the head word and starts over. Otherwise it resets the page, sets the lost flag, and stores the next head word with release ordering. The page is now free, and the writer starts over, which moves the tail onto it.
Each owner CAS reads the previous owner's release store, so every mover sees the pages as the last one left them. A writer that finds the owner bit already set drops its record, and the reader reports Nothing ready.
When the reader delivers a page, it clears the lost flag. If the flag was set, it sets the lost-records bit in its copy of the page header.
The reader rebuilds record times by adding deltas in page order. If a writer read the clock and then claimed its space, a pause between the two could give its record an earlier time than the record before it. Every time after it on the page would then decode wrong, so a record's time and position are decided in the same CAS.
The claim word holds the low bits of the last claimed record's time, about 46 bits, a range of about 19.5 hours. On each claim attempt, a writer reads the clock and the claim word, then:
time_delta holds the low 27 bits.A failed CAS means another record was claimed in between, so the writer reads the clock again and redoes the steps. After a successful claim it writes the time-extend record and the page timestamp, if it has them, and raises the buffer‘s last time to its record’s time. A first record never needs a time-extend record, so any record that fits in the record area fits on an empty page.
Disabling stops new reservations and reads, waits for the ones in progress to finish, and then frees the memory, so no reader or writer is still using it. Every reserve and read enters the buffer with an acquire CAS on the ring word that fails when the enabled bit is clear, and leaves with a release decrement. A reservation stays inside until it is committed. Disable clears the enabled bit and frees the memory only after an acquire read of the ring word shows no reservations or reads in progress, so every access happens before the free. Enable resets every page, puts the head and tail on the same page, and sets the enabled bit with a release store, so every later call sees the reset.
Guarantee 13 says no writer or reader waits for another thread to be scheduled, because that thread may be paused for any length of time. Every step that several threads may want to take is one of two kinds.
Some steps any thread can finish for the others. Moving the tail onto a free page is one: every writer that finds the tail page closed CASes the tail word from the value it read. One CAS wins, and the rest fail, see the new tail, and continue on it. No writer depends on the one that closed the page to move the tail.
Other steps belong to the one thread that won the right to take them: closing a page (won by the atomic OR) and consuming the head (won by the owner bit). Nobody waits for the winner to finish. Writers that find the page closed move the tail and claim space on the next page, writers that find the head owned drop their records, and the reader reports Nothing ready.
A paused writer still delays delivery of its page and the pages after it (see Context), and while a paused reader owns the head, overwriting writers drop their records instead of discarding that page.
Claims use a CAS rather than the atomic add that Linux uses. An add never retries, so it is cheaper when many writers hit one page, but it can‘t make the claim length depend on the value it replaces. Here a record needs 8 more bytes when its delta needs a time-extend record, and the delta depends on the previous record’s time. A CAS only fails when another writer succeeded, so writers still make progress.
The newest page becomes readable only once a write overflows it, because only a writer whose record doesn't fit closes a page. Writers and the reader never contend over the newest page, but its records wait until the next page starts, and disable discards them. Letting the reader close the newest page would make records readable sooner, at the price of a race on the closed bit and partly empty pages.
The reader copies the head page while it stays in the ring. Linux instead swaps a spare page into the ring for the head, so writers can never reach the page being copied. Copying without the swap needs no spare page and no links between pages, and keeps the pages in a fixed order. While the copy runs, though, an overwriting writer that needs that page drops its record.
After hours with no records, a writer starts a new page rather than writing a time-stamp record. That wastes the rest of a page, but only after a long gap, and avoids a record type whose layout changed in Linux 4.17.
A writer that finds a paused writer still active on the head page drops its record rather than wait. Waiting would turn that writer's count into a lock held across a preemption, stalling every writer behind it. Records are lost when the ring wraps onto a paused writer, and they are counted.
Every reservation must be committed with a complete record. Abandoning one would mean turning it into a padding record, which needs a nonzero delta and so shifts the times around it.