Project 4: Memory-Mapped Ring Buffer IPC

Build a zero-copy ring buffer shared between two processes using mmap, with correct ordering, crash detection, and optional durability.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 2-3 weeks
Main Programming Language C (Alternatives: Rust, C++)
Alternative Programming Languages Rust, C++
Coolness Level Level 5 - High-performance IPC
Business Potential Level 4 - Infrastructure building block
Prerequisites mmap basics, structs, atomics
Key Topics MAP_SHARED, ring buffers, memory ordering, crash recovery

1. Learning Objectives

By completing this project, you will:

  1. Implement a shared ring buffer with mmap and MAP_SHARED.
  2. Publish and consume records with correct memory ordering.
  3. Detect and handle partial writes after crashes.
  4. Use msync for optional durability checkpoints.
  5. Benchmark throughput and latency.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Memory Mapping, MAP_SHARED, and File-Backed Shared Memory

Fundamentals

mmap maps a file into a process’s address space so reads and writes happen directly in memory. With MAP_SHARED, changes are visible to other processes that map the same file. This is the foundation of zero-copy IPC: two processes can communicate by writing and reading the same memory. However, MAP_SHARED does not automatically guarantee durability; it guarantees visibility, not persistence. You must manage file sizing, alignment, and synchronization to avoid SIGBUS and data corruption.

Deep Dive into the concept

When you call mmap, the kernel creates virtual memory mappings that reference pages of a file. With MAP_SHARED, writes go to the page cache and are visible to other mappings immediately (subject to CPU cache coherence). The file must be properly sized before mapping; otherwise, writing beyond the end of the file causes a SIGBUS. This is why ftruncate is required before mapping. The mapping length should be page-aligned for efficiency.

Visibility is not the same as durability. A MAP_SHARED write updates the page cache, but the data may not be flushed to disk until later. If the system crashes, data may be lost unless you call msync or fsync. For a ring buffer that is used for IPC, you usually care about visibility, not durability. However, you might want periodic durability checkpoints so that if a producer crashes, a consumer can resume without corrupting data. This is optional but a powerful extension.

Another important detail is how multiple processes coordinate access. mmap does not provide any automatic synchronization. You must ensure that the producer and consumer agree on the memory layout and use atomic operations or memory barriers to maintain ordering. If the producer writes data but the consumer reads the header before the payload is fully written, you can see partial records. This is why ordering rules are essential.

Finally, consider the lifetime of the shared file. If you unlink the file after mapping, the mapping remains valid as long as any process holds it open. This is a useful technique to create ephemeral shared memory that disappears automatically when all processes exit. It mirrors the behavior of anonymous shared memory but gives you a persistent file for debugging.

How this fits in projects

This concept defines the IPC mechanism for Project 4 and is reused in Project 6 if you choose to build high-throughput logging or event streams.

Definitions & key terms

  • mmap: System call to map files into memory.
  • MAP_SHARED: Mapping flag that shares changes across processes.
  • SIGBUS: Signal for invalid memory access, often from writing past mapped file.
  • msync: Flushes changes to disk.

Mental model diagram (ASCII)

Process A          Shared file          Process B
+---------+        +-----------+        +---------+
|  mmap   | <----> | page cache| <----> |  mmap   |
+---------+        +-----------+        +---------+

How it works (step-by-step, with invariants and failure modes)

  1. Create and size a file with ftruncate.
  2. Map it with MAP_SHARED in both processes.
  3. Write data into mapped region.
  4. Reader sees writes without syscalls.
  5. Failure mode: file not sized -> SIGBUS on write.

Minimal concrete example

int fd = open(path, O_RDWR|O_CREAT, 0644);
ftruncate(fd, RING_SIZE);
void *buf = mmap(NULL, RING_SIZE, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);

Common misconceptions

  • “MAP_SHARED makes data durable”: it only makes it visible.
  • “mmap is always faster”: it can be slower if you thrash the cache.

Check-your-understanding questions

  1. Why must you size the file before mmap?
  2. What does MAP_SHARED guarantee?
  3. When should you call msync?

Check-your-understanding answers

  1. Writing past the file end triggers SIGBUS.
  2. Changes are visible to other mappings, not necessarily durable.
  3. When you need durability across crashes.

Real-world applications

  • Shared memory queues in trading systems.
  • IPC between logging agents and consumers.

Where you will apply it

References

  • TLPI Chapter 49 (Memory Mappings).
  • man 2 mmap, man 2 msync.

Key insights

MAP_SHARED gives visibility, not durability.

Summary

Memory mapping enables zero-copy IPC but requires explicit sizing, layout, and ordering.

Homework/exercises to practice the concept

  1. Map a file, write data, and read it from another process.
  2. Try writing past the mapped size and observe SIGBUS.
  3. Use msync and confirm data persistence after crash.

Solutions to the homework/exercises

  1. The second process should see the data immediately.
  2. SIGBUS occurs due to invalid mapping.
  3. With msync, data persists; without it, it may not.

2.2 Ring Buffer Design and Wrap-Around Semantics

Fundamentals

A ring buffer is a fixed-size circular buffer with a head (read position) and tail (write position). When the tail reaches the end, it wraps to the beginning. This is ideal for IPC because it allows continuous streaming without reallocations. However, you must handle wrap-around correctly and detect when the buffer is full or empty. This often involves leaving one slot empty or using sequence numbers to distinguish full from empty.

Deep Dive into the concept

The ring buffer can store variable-length records by using a header that includes record length and a checksum. The producer writes the header and payload, then updates the tail pointer. The consumer reads the header, verifies the checksum, and then reads the payload. Wrap-around adds complexity: if a record does not fit at the end, the producer can either wrap and insert a padding record or store a special “wrap” marker. The consumer must recognize this and move to the start.

To avoid ambiguity between full and empty states, you can use sequence numbers or store the amount of data in the buffer. A simple approach is to keep head and tail as monotonic counters rather than indices, and compute index as counter % capacity. Full condition is when tail - head >= capacity. Empty when tail == head. This approach avoids wrap ambiguity and supports large counters.

The buffer must also handle overwrite policies. Some systems choose “drop new” when full; others “drop old” by advancing head. For a log stream, dropping old data may be acceptable, but for reliable messaging, you should block the producer or return an error. This is a key design decision.

How this fits in projects

Ring buffer logic is the core of Project 4. It also appears in Project 6 if you use ring buffers for log or event streaming.

Definitions & key terms

  • Head: Read position.
  • Tail: Write position.
  • Capacity: Total size of buffer.
  • Wrap marker: Record that indicates wrap-around.

Mental model diagram (ASCII)

[0.............N]
 ^head      ^tail
wrap -> tail moves to 0

How it works (step-by-step, with invariants and failure modes)

  1. Producer reads head and tail.
  2. Compute available space.
  3. If record fits, write header + payload.
  4. Update tail atomically.
  5. Consumer reads head, validates record, advances head.
  6. Failure mode: tail overtakes head -> data corruption.

Minimal concrete example

uint64_t head = atomic_load(&rb->head);
uint64_t tail = atomic_load(&rb->tail);
size_t used = tail - head;

Common misconceptions

  • “Wrap-around is just modulo”: you must handle record boundaries.
  • “Full and empty are easy”: without sequence numbers, they can be ambiguous.

Check-your-understanding questions

  1. How do you distinguish full from empty?
  2. What happens if a record crosses the end of the buffer?
  3. When should you drop data vs block?

Check-your-understanding answers

  1. Use monotonic counters and compare difference.
  2. Insert a wrap marker or pad, then wrap to start.
  3. It depends on reliability requirements; make it explicit.

Real-world applications

  • Audio buffers in real-time systems.
  • Network packet queues.

Where you will apply it

References

  • “The Art of Multiprocessor Programming” for ring buffer patterns.

Key insights

Ring buffers require explicit policies for full, empty, and wrap-around.

Summary

A correct ring buffer uses monotonic counters, explicit wrap markers, and clear drop policies.

Homework/exercises to practice the concept

  1. Implement a ring buffer with fixed-size records.
  2. Extend it to variable-length records with a header.
  3. Simulate full buffer conditions and test drop/block behavior.

Solutions to the homework/exercises

  1. The buffer should maintain head and tail correctly.
  2. Records should parse correctly across wrap boundaries.
  3. The chosen policy should match your design.

2.3 Memory Ordering and Atomic Publication

Fundamentals

When two processes share memory, the order of reads and writes matters. CPUs and compilers can reorder operations for performance. Without explicit memory ordering, a consumer might see the tail pointer updated before the payload is fully written, leading to partial reads. Atomic operations with release/acquire semantics ensure that writes are visible in the correct order. The producer should write the payload, then publish the tail with a release store. The consumer should load the tail with acquire semantics before reading data.

Deep Dive into the concept

Modern CPUs use caches and out-of-order execution. This means that writes in program order do not necessarily appear in memory in the same order. Compilers also reorder instructions unless told otherwise. In a shared memory IPC, this can lead to subtle corruption: the producer updates the tail pointer (which signals new data) before the payload is fully visible. The consumer reads the tail, sees new data, and then reads stale or partial payload. This is a classic memory ordering bug.

C11 atomics provide a portable way to express ordering. A release store ensures that all prior writes in the same thread become visible before the store. An acquire load ensures that subsequent reads see the writes that happened-before the release. The correct pattern is: producer writes payload and header, then performs atomic_store_explicit(&tail, new_tail, memory_order_release). Consumer performs atomic_load_explicit(&tail, memory_order_acquire) and then reads payload. This establishes a happens-before relationship.

If you use non-atomic operations or relaxed order, you can experience rare, non-deterministic bugs that are extremely hard to reproduce. For a teaching project, you can include a mode that intentionally uses relaxed ordering to show the failure under stress. This is a powerful demonstration of how systems fail in production without proper memory ordering.

How this fits in projects

This concept is central to correctness in Project 4 and is directly used in the publish/consume logic.

Definitions & key terms

  • Release: Memory ordering that ensures prior writes are visible.
  • Acquire: Memory ordering that ensures subsequent reads see prior writes.
  • Happens-before: Ordering relationship that guarantees visibility.

Mental model diagram (ASCII)

Producer: write payload -> write header -> store tail (release)
Consumer: load tail (acquire) -> read header/payload

How it works (step-by-step, with invariants and failure modes)

  1. Producer writes payload bytes.
  2. Producer writes header with length and checksum.
  3. Producer performs release store of tail.
  4. Consumer loads tail with acquire.
  5. Consumer reads header and payload.
  6. Failure mode: tail updated before payload visible.

Minimal concrete example

atomic_store_explicit(&rb->tail, new_tail, memory_order_release);
uint64_t tail = atomic_load_explicit(&rb->tail, memory_order_acquire);

Common misconceptions

  • “Shared memory is automatically ordered”: it is not.
  • “Volatile fixes ordering”: volatile does not guarantee ordering.

Check-your-understanding questions

  1. Why is memory ordering needed even with a single producer and consumer?
  2. What happens if you update tail before payload?
  3. Why is volatile insufficient?

Check-your-understanding answers

  1. CPUs can reorder and cache writes, causing visibility issues.
  2. The consumer can read partial or stale data.
  3. Volatile only prevents some compiler optimizations, not CPU reordering.

Real-world applications

  • Lock-free queues.
  • Shared memory IPC in high-frequency trading.

Where you will apply it

References

  • “C11 Atomics and Locks” (resources on memory ordering).
  • “The Art of Multiprocessor Programming”.

Key insights

Publication order is as important as the data itself.

Summary

Use release/acquire semantics to ensure consumers see complete records.

Homework/exercises to practice the concept

  1. Implement producer/consumer with relaxed atomics and stress test.
  2. Replace with release/acquire and compare error rates.
  3. Explain happens-before relationships in your own words.

Solutions to the homework/exercises

  1. Relaxed ordering can yield corrupted reads under stress.
  2. Release/acquire eliminates visibility bugs.
  3. Happens-before ensures visibility and ordering across threads/processes.

2.4 Crash Consistency and Partial Write Detection

Fundamentals

When a producer crashes mid-write, the consumer may see a partially written record. To detect this, records should include a header with length and checksum or a commit marker. The consumer should verify integrity before accepting a record. If verification fails, it should treat the record as incomplete and wait or skip, depending on policy.

Deep Dive into the concept

Crash consistency is about ensuring data structures remain in a recoverable state after failure. For a ring buffer, this means that each record must be either fully written or clearly incomplete. A common technique is to write the payload first, then write the header last. The header includes a length and a checksum. The consumer reads the header; if the checksum does not match the payload, it treats the record as incomplete. Another approach is to write a “commit” flag at the end of the record; the consumer only accepts records with a commit flag set.

The ring buffer should also include a version and magic number to ensure the reader can validate the structure before reading. On restart, the reader can scan for valid records and skip corrupt sections. This is similar to WAL (write-ahead logging) techniques, where a record is only considered valid if it is fully written and has a valid checksum.

A policy decision is whether to block when encountering a partial record or to skip it and continue. For IPC, it may be better to block and wait for a producer restart, because skipping could desynchronize the stream. For a log stream where some loss is acceptable, you might skip after a timeout. This should be configurable and documented.

How this fits in projects

Partial write detection is critical for Project 4 correctness and is a core part of crash recovery behavior.

Definitions & key terms

  • Checksum: Hash to validate record integrity.
  • Commit marker: A flag indicating a complete record.
  • Crash consistency: Ability to recover after failure.

Mental model diagram (ASCII)

write payload -> write header -> publish tail
(crash before header) => reader sees incomplete

How it works (step-by-step, with invariants and failure modes)

  1. Producer writes payload bytes.
  2. Producer computes checksum.
  3. Producer writes header last.
  4. Consumer reads header, verifies checksum.
  5. If invalid, treat as partial and wait.
  6. Failure mode: consumer trusts partial record.

Minimal concrete example

struct rec_hdr { uint32_t len; uint32_t crc; };

Common misconceptions

  • “If the tail moved, the record is valid”: tail can be updated prematurely if ordering is wrong.
  • “Checksum is optional”: without it, partial writes are indistinguishable from valid data.

Check-your-understanding questions

  1. Why write the header last?
  2. What should the consumer do if checksum fails?
  3. How does this relate to WAL semantics?

Check-your-understanding answers

  1. It serves as a commit marker after payload is complete.
  2. Treat as incomplete and wait or skip based on policy.
  3. Both use checksums and commit markers to ensure validity.

Real-world applications

  • WAL files in databases.
  • Message queues using shared memory.

Where you will apply it

References

  • “Designing Data-Intensive Applications” (durability patterns).

Key insights

A record is valid only if it is fully written and verifiable.

Summary

Crash consistency requires explicit integrity checks and a clear commit sequence.

Homework/exercises to practice the concept

  1. Implement a header+payload record and verify checksum.
  2. Simulate a crash by killing the producer mid-write.
  3. Implement a recovery scan that skips invalid records.

Solutions to the homework/exercises

  1. The checksum should match for valid records.
  2. The consumer should detect the partial record and wait/skip.
  3. The scan should stop or skip based on policy.

3. Project Specification

3.1 What You Will Build

A pair of programs: writer and reader, communicating via a memory-mapped ring buffer stored in a shared file. The writer publishes records, and the reader consumes them with minimal latency and correct ordering. Optional msync checkpoints allow durability testing.

3.2 Functional Requirements

  1. Shared buffer: Memory-mapped file shared between two processes.
  2. Ring buffer: Correct wrap-around and full/empty handling.
  3. Ordering: Release/acquire ordering for tail/head updates.
  4. Crash detection: Detect partial writes via checksums.
  5. Optional durability: msync checkpoints.

3.3 Non-Functional Requirements

  • Performance: >100k messages/sec on a laptop.
  • Reliability: No corrupted reads under stress.
  • Usability: Clear stats output.

3.4 Example Usage / Output

$ ./writer --rate 100000
[writer] wrote 100k msgs/sec into ring

$ ./reader
[reader] msg=932183 latency=220us
[reader] msg=932184 latency=210us

3.5 Data Formats / Schemas / Protocols

Record format:

| len (u32) | crc (u32) | payload bytes... |

Shared header:

struct ring_header {
    uint64_t head;
    uint64_t tail;
    uint32_t capacity;
    uint32_t magic;
};

3.6 Edge Cases

  • Writer crashes mid-record.
  • Reader lags and buffer becomes full.
  • Wrap marker at end of buffer.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

make
./writer --file /tmp/ring.dat --rate 50000
./reader --file /tmp/ring.dat

3.7.2 Golden Path Demo (Deterministic)

  • Use fixed payload sequence and seed for random sizes.
  • Reader shows monotonically increasing IDs.

3.7.3 If CLI: exact terminal transcript

$ ./writer --file /tmp/ring.dat --rate 1000 --seed 1
[writer] wrote 1000 msgs/sec

$ ./reader --file /tmp/ring.dat
[reader] msg=1 latency=200us
[reader] msg=2 latency=210us

Failure demo (partial write):

$ ./writer --crash-after 3
[writer] crashed after partial write
$ ./reader
[reader] detected incomplete record, waiting

Exit codes:

  • 0 on clean exit.
  • 6 on corrupted ring header.

4. Solution Architecture

4.1 High-Level Design

+-------------------+   mmap   +-------------------+
| Writer Process    | <------> | Reader Process    |
+---------+---------+          +---------+---------+
          |                              |
      ring buffer in shared file (MAP_SHARED)

4.2 Key Components

Component Responsibility Key Decisions
Shared header head/tail, magic, capacity Atomic head/tail
Writer Publish records with checksum Header written last
Reader Validate and consume records Acquire load of tail
Stats Throughput and latency Simple counters

4.3 Data Structures (No Full Code)

struct rec_hdr { uint32_t len; uint32_t crc; };
struct ring {
    _Atomic uint64_t head;
    _Atomic uint64_t tail;
    uint32_t capacity;
    uint32_t magic;
    char data[];
};

4.4 Algorithm Overview

Key Algorithm: Publish/consume

  1. Writer checks available space.
  2. Writer writes payload, then header.
  3. Writer updates tail with release store.
  4. Reader loads tail with acquire, validates header.
  5. Reader advances head after consuming.

Complexity Analysis:

  • Time: O(1) per record.
  • Space: O(capacity).

5. Implementation Guide

5.1 Development Environment Setup

sudo apt-get install -y gcc make

5.2 Project Structure

ring-ipc/
├── src/
│   ├── writer.c
│   ├── reader.c
│   ├── ring.c
│   └── crc.c
├── include/
│   └── ring.h
├── tests/
│   ├── crash.sh
│   └── wrap.sh
└── Makefile

5.3 The Core Question You’re Answering

“How do I share data between processes without syscalls, safely?”

5.4 Concepts You Must Understand First

  1. mmap and MAP_SHARED semantics.
  2. Ring buffer wrap-around logic.
  3. Memory ordering with release/acquire.
  4. Partial write detection.

5.5 Questions to Guide Your Design

  1. Do you drop or block when the ring is full?
  2. What record format makes partial writes detectable?
  3. How will you ensure memory ordering correctness?

5.6 Thinking Exercise

Partial Write Scenario

Writer writes header len=100 then crashes before payload.
What should the reader do?

5.7 The Interview Questions They’ll Ask

  1. What does MAP_SHARED guarantee?
  2. Why do you need memory barriers in shared memory?
  3. How do you detect partial writes?

5.8 Hints in Layers

Hint 1: ftruncate before mmap

ftruncate(fd, RING_SIZE);

Hint 2: Header last

write payload -> write header -> publish tail

Hint 3: Release/acquire

atomic_store_explicit(&tail, new_tail, memory_order_release);

Hint 4: CRC

uint32_t crc = crc32(payload, len);

5.9 Books That Will Help

Topic Book Chapter
Memory mappings TLPI Ch. 49
Virtual memory CS:APP Ch. 9
Memory ordering C11 Atomics and Locks Ch. 3

5.10 Implementation Phases

Phase 1: Shared Mapping (3-4 days)

Goals:

  • Map shared file and basic writer/reader.

Tasks:

  1. Create file, ftruncate, mmap in both processes.
  2. Implement simple fixed-size record write/read.

Checkpoint: Reader sees data written by writer.

Phase 2: Ring Buffer + Ordering (5-7 days)

Goals:

  • Wrap-around handling and release/acquire ordering.

Tasks:

  1. Implement ring with head/tail counters.
  2. Add atomic ordering and record headers.

Checkpoint: Stress test yields no corruption.

Phase 3: Crash Recovery + Durability (4-6 days)

Goals:

  • Detect partial writes and optional msync.

Tasks:

  1. Implement checksum validation.
  2. Add crash simulation and recovery logic.
  3. Add msync checkpoints.

Checkpoint: Reader handles partial writes safely.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Full buffer policy block, drop-old, drop-new block or drop-new Avoid silent data loss
Record integrity checksum, commit flag checksum + header last Detect partial writes
Durability none, msync checkpoint optional msync IPC usually needs visibility only

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests CRC correctness crc test
Integration Tests Wrap-around and ordering wrap.sh
Edge Case Tests Crash mid-write crash.sh

6.2 Critical Test Cases

  1. Writer crashes mid-record; reader detects incomplete record.
  2. Wrap-around record parsed correctly.
  3. Ordering remains correct under stress.

6.3 Test Data

Record payload: "msg-0001"
Expected crc: <computed value>

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Missing ftruncate SIGBUS Size file before mmap
No ordering barriers Corrupted reads Release/acquire atomics
No checksum Partial writes accepted Validate integrity

7.2 Debugging Strategies

  • Use hexdump to inspect shared file contents.
  • Add a debug mode that prints head/tail positions.
  • Stress with small buffer size to force wrap-around.

7.3 Performance Traps

  • Using msync on every record (too slow).
  • Oversized records causing frequent wrap markers.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a stats-only reader that counts messages.
  • Implement fixed-size records only.

8.2 Intermediate Extensions

  • Add multiple readers with independent head pointers.
  • Implement a blocking wait with futexes.

8.3 Advanced Extensions

  • Add lock-free multi-producer support.
  • Persist checkpoints for restart recovery.

9. Real-World Connections

9.1 Industry Applications

  • HFT systems: shared memory queues for market data.
  • Logging pipelines: low-latency event streaming.
  • LMAX Disruptor: ring buffer pattern.
  • Chronicle Queue: high-performance IPC.

9.3 Interview Relevance

  • Memory ordering and shared memory are advanced systems topics.

10. Resources

10.1 Essential Reading

  • The Linux Programming Interface - mmap and shared memory.
  • C11 Atomics and Locks - ordering semantics.

10.2 Video Resources

  • Talks on lock-free queues and shared memory.

10.3 Tools & Documentation

  • man 2 mmap, man 2 msync, man 2 ftruncate.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain MAP_SHARED vs MAP_PRIVATE.
  • I can explain release/acquire ordering.
  • I can detect partial writes.

11.2 Implementation

  • All functional requirements are met.
  • Stress tests show no corruption.
  • Crash recovery works.

11.3 Growth

  • I can justify my buffer-full policy.
  • I can explain why msync is optional.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Shared ring buffer works across two processes.
  • Correct wrap-around and ordering.
  • Partial writes detected.

Full Completion:

  • Benchmarks reported and crash recovery tested.
  • Optional durability with msync.

Excellence (Going Above & Beyond):

  • Multi-producer support or futex-based waiting.
  • Persistent recovery across restarts.