Project 1: IPC Message Passing Library

Build a user-space synchronous IPC library with endpoints, rendezvous, and a call-reply pattern.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 1 week
Language C (Alternatives: Rust, C++)
Prerequisites Threads, mutex/condvar basics, process model
Key Topics Synchronous IPC, rendezvous, deadlock, zero-copy

1. Learning Objectives

By completing this project, you will:

  1. Implement synchronous IPC semantics with send/receive rendezvous.
  2. Design endpoint data structures that safely handle concurrent clients.
  3. Analyze IPC performance and reduce copies on the critical path.
  4. Explain why microkernels place IPC at the center of system design.

2. Theoretical Foundation

2.1 Core Concepts

  • Synchronous IPC (Rendezvous): Sender and receiver meet; both block until the transfer completes. This eliminates queues and enforces backpressure.
  • Endpoints and Ports: An endpoint is the kernel-visible rendezvous point. It’s not a queue; it’s a place to meet.
  • Copy vs Map: Copying data across address spaces is easy but slow; mapping shared pages is fast but requires careful lifetime and permission management.
  • Deadlock in IPC Graphs: Cycles of blocking sends/receives can deadlock unless you define ordering or timeouts.

2.2 Why This Matters

Microkernels push services to user space. IPC becomes the “system call” of everything: filesystem, networking, drivers, and supervisors. If IPC is slow or buggy, the entire OS is slow or buggy.

2.3 Historical Context / Background

Mach’s IPC was flexible but slow, causing early microkernels to miss performance targets. L4 reframed IPC for speed by minimizing copies and context-switch overhead. seL4 formalized IPC semantics and verified correctness.

2.4 Common Misconceptions

  • “IPC is just a queue.” Synchronous IPC is about rendezvous, not buffering.
  • “Copying is unavoidable.” It’s avoidable for large payloads by mapping pages.
  • “Deadlock is rare.” Any blocking protocol can deadlock without clear ordering.

3. Project Specification

3.1 What You Will Build

A user-space library that exposes endpoints, message types, and send/receive/call APIs. The library should support multiple clients, timeouts, and a simple reply channel.

3.2 Functional Requirements

  1. Endpoint Creation: Create/destroy endpoints and register them by name.
  2. Synchronous Send/Receive: Implement blocking send and receive with rendezvous semantics.
  3. Call/Reply: Implement a call API that sends a request and waits for a reply from the server.
  4. Timeouts: Support timeouts on send/receive to avoid deadlock.
  5. Multiple Clients: Correctly handle concurrent senders to a single endpoint.

3.3 Non-Functional Requirements

  • Performance: Minimize critical-path copies for small messages.
  • Reliability: No deadlocks under the defined protocol and timeouts.
  • Usability: Clear C API with simple error codes.

3.4 Example Usage / Output

endpoint_t ep = endpoint_create("echo");

// Server thread
message_t msg;
client_t sender = receive(ep, &msg);
message_t reply = { .data = "ACK" };
send(sender, &reply);

// Client thread
endpoint_t server = endpoint_lookup("echo");
message_t req = { .data = "Hello" };
message_t resp;
call(server, &req, &resp);

3.5 Real World Outcome

Run the demo server and client to see rendezvous and reply:

$ ./ipc_demo
[server] endpoint "echo" ready
[client] sending "Hello"
[server] received: Hello
[client] reply: ACK
[stats] rendezvous latency: 4.8 us

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐      send/recv      ┌──────────────┐
│   Client     │  ───────────────▶   │   Endpoint   │
│ (Thread/Proc)│  ◀───────────────   │  (Rendezvous)│
└──────────────┘                      └──────┬───────┘
                                             │
                                             ▼
                                      ┌──────────────┐
                                      │   Server     │
                                      └──────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Endpoint Rendezvous point and queues Single lock vs per-queue locks
Wait queues Track blocked senders/receivers FIFO for fairness
Message buffers Store payloads Inline small payloads, pointer for large
Registry Name lookup Global hash map with RW lock

4.3 Data Structures

typedef struct message {
    uint32_t len;
    uint8_t data[256];
} message_t;

typedef struct waiter {
    pthread_cond_t cv;
    message_t *msg;
    int ready;
    struct waiter *next;
} waiter_t;

typedef struct endpoint {
    char name[64];
    pthread_mutex_t lock;
    waiter_t *senders;
    waiter_t *receivers;
} endpoint_t;

4.4 Algorithm Overview

Key Algorithm: Rendezvous Send/Receive

  1. Sender acquires endpoint lock.
  2. If a receiver is waiting, copy message and wake receiver.
  3. Otherwise enqueue sender and block.
  4. Receiver performs the symmetric logic.

Complexity Analysis:

  • Time: O(1) average for queue head operations
  • Space: O(N) for number of waiting threads

5. Implementation Guide

5.1 Development Environment Setup

# Linux/macOS
cc -pthread -O2 -g -o ipc_demo *.c

5.2 Project Structure

ipc-lib/
├── src/
│   ├── endpoint.c
│   ├── ipc.c
│   ├── registry.c
│   └── main.c
├── include/
│   └── ipc.h
├── tests/
│   └── test_ipc.c
└── Makefile

5.3 The Core Question You’re Answering

“How can two isolated processes exchange data without sharing memory or trusting each other?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Condition Variables and Spurious Wakeups
    • Why must you re-check conditions after waking?
  2. Blocking vs Busy Waiting
    • How does a blocked thread get rescheduled?
  3. Race Conditions in Queue Management
    • What happens if a sender and receiver arrive simultaneously?
  4. Deadlock and Timeouts
    • How do timeouts avoid circular waits?

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Should send/receive be FIFO or priority based?
  2. How do you return errors (timeout, endpoint not found)?
  3. Where do you store large messages without copying?
  4. How do you prevent a malicious client from starving others?

5.6 Thinking Exercise

Trace a Rendezvous by Hand

Imagine sender S arrives, then sender T, then receiver R. Draw a timeline of which threads block and which wake. Now reverse the order: receiver first, then senders.

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is rendezvous IPC and why is it efficient?”
  2. “How do you avoid deadlocks in a synchronous IPC system?”
  3. “What is the cost of a context switch, and why does it matter?”

5.8 Hints in Layers

Hint 1: Start with a single sender/receiver Build a minimal happy path before concurrency.

Hint 2: Add queues Introduce linked lists for blocked senders/receivers.

Hint 3: Add timeouts Use pthread_cond_timedwait to avoid permanent blocking.

5.9 Books That Will Help

Topic Book Chapter
IPC fundamentals OSTEP IPC chapter
Synchronization OSTEP Concurrency chapters
Microkernel IPC L4 papers Sections on IPC

5.10 Implementation Phases

Phase 1: Foundation (2 days)

Goals:

  • Endpoint creation and lookup
  • Basic send/receive

Tasks:

  1. Build endpoint registry with a hash map.
  2. Implement send/receive with a single waiting pair.

Checkpoint: A single client and server can exchange a message.

Phase 2: Core Functionality (3 days)

Goals:

  • Multiple clients and fairness
  • Call/reply API

Tasks:

  1. Add sender/receiver queues.
  2. Implement call() as send + receive.

Checkpoint: Two clients can call the server concurrently.

Phase 3: Polish & Edge Cases (2 days)

Goals:

  • Timeouts
  • Performance metrics

Tasks:

  1. Add timed waits and timeout errors.
  2. Measure latency with a microbenchmark.

Checkpoint: Timeout returns are correct and benchmark runs.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Queue policy FIFO, priority FIFO Predictable and fair
Message storage Copy, shared memory Copy for small, map for large Simple first, optimize later
Synchronization Global lock, per-endpoint Per-endpoint Reduces contention

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate endpoint behavior Create/destroy, lookup
Integration Tests Client-server exchange call/receive with replies
Edge Case Tests Timeouts, multiple clients 100 concurrent senders

6.2 Critical Test Cases

  1. Receiver-first rendezvous: Receiver blocks, sender wakes it, transfer succeeds.
  2. Sender-first rendezvous: Sender blocks, receiver wakes it, transfer succeeds.
  3. Timeout: Sender with no receiver returns ETIMEDOUT.

6.3 Test Data

Messages: "ping", "long message...", empty payload
Clients: 1, 2, 100
Timeouts: 1ms, 10ms, 100ms

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Lost wakeup Both sides block forever Always signal under lock and re-check condition
Double free of waiter Crashes under load Define clear ownership of waiter nodes
Busy waiting High CPU usage Use condition variables, not spin loops

7.2 Debugging Strategies

  • Thread sanitizer: Use -fsanitize=thread to catch data races.
  • Trace logs: Log state transitions for send/receive and queue length.

7.3 Performance Traps

If you copy large buffers on every call, IPC becomes slower than syscalls. Move large payloads to shared memory after the prototype is correct.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add statistics (messages sent, average latency).
  • Implement named endpoints with permissions.

8.2 Intermediate Extensions

  • Add a shared-memory fast path for large payloads.
  • Implement priority queues for real-time workloads.

8.3 Advanced Extensions

  • Add capability-based endpoint access (ties into Project 2).
  • Implement cross-process zero-copy with page remapping.

9. Real-World Connections

9.1 Industry Applications

  • seL4: All system services talk via IPC endpoints.
  • QNX: Message passing is the OS API.
  • seL4: https://sel4.systems/ - Verified microkernel IPC.
  • L4Re/Fiasco.OC: https://os.inf.tu-dresden.de/L4/ - Fast IPC implementations.

9.3 Interview Relevance

  • IPC, synchronization, and deadlock questions are common in OS interviews.

10. Resources

10.1 Essential Reading

  • Operating Systems: Three Easy Pieces by Arpaci-Dusseau - IPC and concurrency sections.
  • L4 Microkernels: Lessons from 20 Years - IPC design lessons.

10.2 Video Resources

  • IPC and microkernel lectures from OS courses (MIT 6.S081).

10.3 Tools & Documentation

  • pthread: man pthread_cond_wait
  • perf: basic latency measurements
  • Project 2: Builds on IPC to secure access.
  • Project 4: Implements IPC in a real kernel.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain rendezvous IPC without notes.
  • I can describe how an endpoint prevents data races.
  • I can explain the performance cost of a context switch.

11.2 Implementation

  • All functional requirements are met.
  • Tests cover sender-first and receiver-first cases.
  • Timeouts behave correctly.

11.3 Growth

  • I can describe one optimization I would add next.
  • I can explain my design in an interview setting.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Endpoint creation and lookup work.
  • Synchronous send/receive works with one client.
  • A call-reply example runs correctly.

Full Completion:

  • Multiple clients handled concurrently.
  • Timeouts and errors reported correctly.

Excellence (Going Above & Beyond):

  • Zero-copy path for large messages.
  • Microbenchmark results documented.

This guide was generated from LEARN_MICROKERNELS.md. For the complete learning path, see the parent directory.