I/O Architecture: How the CPU Communicates with the World

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

/*
 * DMA Descriptor Structures
 * 
 * Modern DMA uses descriptor rings - the device fetches transfer
 * descriptions from memory, executes them, and updates completion status.
 */
 
#include <stdint.h>
 
/*
 * Simple DMA Descriptor (generic pattern)
 * 
 * Each descriptor describes one contiguous memory region
 * for a DMA transfer.
 */
struct dma_descriptor {
    uint64_t buffer_addr;     /* Physical address of data buffer */
    uint32_t buffer_length;   /* Length in bytes */
    uint32_t control;         /* Flags: interrupt-on-complete, etc. */
} __attribute__((packed));
 
/* Control word flags */
#define DMA_CTRL_INTR   (1 << 0)   /* Generate interrupt on completion */
#define DMA_CTRL_LINK   (1 << 1)   /* Another descriptor follows */
#define DMA_CTRL_LAST   (1 << 2)   /* This is the last descriptor */
 
/*
 * NVMe-style Submission Queue Entry (Simplified)
 * 
 * NVMe uses command queues rather than simple descriptors.
 * Each entry is a 64-byte command that can reference multiple
 * Physical Region Pages.
 */
struct nvme_sqe {
    uint8_t opcode;           /* Command opcode (read, write, etc.) */
    uint8_t flags;            /* Fused command, PRP vs SGL, etc. */
    uint16_t command_id;      /* Unique ID for completion matching */
    uint32_t nsid;            /* Namespace ID */
    uint64_t reserved;
    uint64_t metadata;        /* Metadata buffer address */
    uint64_t prp1;            /* Physical Region Page 1 (data buffer) */
    uint64_t prp2;            /* PRP 2 or PRP list pointer */
    uint32_t cdw10;           /* Command-specific dword 10 */
    uint32_t cdw11;           /* Start LBA (low 32 bits for read/write) */
    uint32_t cdw12;           /* LBA (high 32 bits) */
    uint32_t cdw13;           /* Command-specific */
    uint32_t cdw14;           /* Command-specific */
    uint32_t cdw15;           /* Command-specific */
} __attribute__((packed));
 
/*
 * Scatter-Gather List Entry (Intel Style)
 * 
 * Describes one segment of a potentially non-contiguous buffer.
 * Multiple SGEs form a list, allowing DMA to access scattered pages.
 */
struct sg_entry {
    uint64_t address;         /* Physical address of segment */
    uint32_t length;          /* Segment length in bytes */
    uint32_t flags;           /* End-of-list, interrupt, etc. */
} __attribute__((packed));
 
/* SG flags */
#define SG_FLAG_FINAL   (1 << 31)  /* Last entry in list */
 
/*
 * DMA Ring Buffer (Descriptor Ring)
 * 
 * Many devices use circular descriptor rings for efficient
 * command submission and completion.
 */
#define RING_SIZE 256
 
struct dma_ring {
    struct dma_descriptor descriptors[RING_SIZE];  /* In DMA-able memory */
    volatile uint32_t head;                         /* Next to submit */
    volatile uint32_t tail;                         /* Next to complete */
    uint32_t ring_size;
    
    /* Shadow data for driver use (not touched by hardware) */
    void *buffers[RING_SIZE];         /* Virtual addresses of buffers */
    void *completion_data[RING_SIZE]; /* Per-descriptor completion context */
};
 
/*
 * Ring buffer management
 */
static inline bool ring_full(struct dma_ring *ring) {
    return ((ring->head + 1) % ring->ring_size) == ring->tail;
}
 
static inline bool ring_empty(struct dma_ring *ring) {
    return ring->head == ring->tail;
}
 
static inline uint32_t ring_next(struct dma_ring *ring, uint32_t idx) {
    return (idx + 1) % ring->ring_size;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

/*
 * Scatter-Gather DMA Implementation
 * 
 * Demonstrates building and using scatter-gather lists for
 * DMA transfers with non-contiguous physical memory.
 */
 
#include <stdint.h>
#include <stddef.h>
 
/* Simulated kernel functions */
extern uint64_t virt_to_phys(void *virt);
extern void *dma_alloc_coherent(size_t size, uint64_t *dma_handle);
extern void dma_free_coherent(void *virt, size_t size, uint64_t dma_handle);
 
/* Page size definitions */
#define PAGE_SIZE       4096
#define PAGE_MASK       (~(PAGE_SIZE - 1))
 
#define MAX_SG_ENTRIES  128
 
/* Scatter-Gather Entry */
struct sg_entry {
    uint64_t dma_address;   /* Physical/DMA address */
    uint32_t length;        /* Length of this segment */
    uint32_t offset;        /* Offset within page (for alignment) */
    struct sg_entry *next;  /* Link to next entry (optional) */
};
 
/* Scatter-Gather Table */
struct sg_table {
    struct sg_entry *entries;   /* Array of entries */
    int nents;                  /* Number of entries in use */
    int max_ents;               /* Maximum entries allocated */
};
 
/*
 * Map a user buffer to a scatter-gather list
 * 
 * Takes a virtually contiguous buffer that may be physically
 * scattered across multiple pages, and creates a list of
 * physical address/length pairs for DMA.
 */
int sg_map_buffer(struct sg_table *sgt, void *buffer, size_t length) {
    uint8_t *ptr = (uint8_t *)buffer;
    size_t remaining = length;
    int entry_idx = 0;
    
    while (remaining > 0 && entry_idx < sgt->max_ents) {
        struct sg_entry *entry = &sgt->entries[entry_idx];
        
        /* Calculate offset within current page */
        uint32_t page_offset = (uintptr_t)ptr & (PAGE_SIZE - 1);
        
        /* Calculate how much we can transfer from this page */
        uint32_t this_seg_len = PAGE_SIZE - page_offset;
        if (this_seg_len > remaining) {
            this_seg_len = remaining;
        }
        
        /* Translate virtual to physical/DMA address */
        entry->dma_address = virt_to_phys(ptr);
        entry->length = this_seg_len;
        entry->offset = page_offset;
        
        ptr += this_seg_len;
        remaining -= this_seg_len;
        entry_idx++;
    }
    
    if (remaining > 0) {
        return -1;  /* Buffer too large for SG table */
    }
    
    sgt->nents = entry_idx;
    return 0;
}
 
/*
 * Program device with scatter-gather list
 * 
 * The device's DMA engine will fetch each entry and transfer
 * data to/from the specified physical addresses.
 */
void program_sg_dma(void *device_base, struct sg_table *sgt, int direction) {
    /* First, allocate DMA-able memory for the SG list itself */
    /* The device needs to read the SG entries from memory */
    
    size_t sg_list_size = sgt->nents * sizeof(struct hw_sg_entry);
    uint64_t sg_dma_addr;
    struct hw_sg_entry *hw_sg = dma_alloc_coherent(sg_list_size, &sg_dma_addr);
    
    /* Copy our SG entries to the hardware format */
    for (int i = 0; i < sgt->nents; i++) {
        hw_sg[i].address = sgt->entries[i].dma_address;
        hw_sg[i].length = sgt->entries[i].length;
        hw_sg[i].flags = (i == sgt->nents - 1) ? SG_FLAG_FINAL : 0;
    }
    
    /* Program device registers with SG list location */
    mmio_write64(device_base + DMA_SG_ADDR, sg_dma_addr);
    mmio_write32(device_base + DMA_SG_COUNT, sgt->nents);
    mmio_write32(device_base + DMA_CONTROL, 
                 (direction == DMA_TO_DEVICE) ? DMA_CTRL_WRITE : DMA_CTRL_READ);
    
    /* Start the DMA (device fetches SG list and begins transfer) */
    mmio_write32(device_base + DMA_COMMAND, DMA_CMD_START);
}
 
/*
 * Coalesce adjacent SG entries
 * 
 * If virtual pages happen to be physically contiguous,
 * we can merge SG entries for better DMA efficiency.
 */
void sg_coalesce(struct sg_table *sgt) {
    if (sgt->nents <= 1) return;
    
    int write_idx = 0;
    
    for (int i = 1; i < sgt->nents; i++) {
        struct sg_entry *prev = &sgt->entries[write_idx];
        struct sg_entry *curr = &sgt->entries[i];
        
        /* Check if this entry is contiguous with previous */
        if (prev->dma_address + prev->length == curr->dma_address) {
            /* Merge: extend previous entry */
            prev->length += curr->length;
        } else {
            /* Not contiguous: start new entry */
            write_idx++;
            if (write_idx != i) {
                sgt->entries[write_idx] = *curr;
            }
        }
    }
    
    sgt->nents = write_idx + 1;  /* Update count after coalescing */
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

/*
 * DMA Cache Management
 * 
 * Proper cache handling is CRITICAL for DMA correctness.
 * Incorrect cache management causes subtle, intermittent data corruption.
 */
 
#include <stdint.h>
#include <stddef.h>
 
/* 
 * DMA direction flags 
 */
#define DMA_TO_DEVICE     1   /* CPU → Memory → Device (device reads) */
#define DMA_FROM_DEVICE   2   /* Device → Memory → CPU (device writes) */
#define DMA_BIDIRECTIONAL 3   /* Both directions */
 
/* Cache line size (architecture dependent) */
#define CACHE_LINE_SIZE 64
 
/* Cache operation primitives (architecture-specific) */
extern void cache_flush_range(void *start, size_t len);      /* Writeback to memory */
extern void cache_invalidate_range(void *start, size_t len); /* Discard cached data */
extern void cache_flush_invalidate_range(void *start, size_t len); /* Both */
 
/*
 * Prepare buffer for DMA transfer (BEFORE starting DMA)
 * 
 * Called after CPU has written data that device will read,
 * or before device will write data that CPU will read.
 */
void dma_sync_for_device(void *buffer, size_t length, int direction) {
    switch (direction) {
        case DMA_TO_DEVICE:
            /*
             * CPU has written data, device will read.
             * Ensure all CPU writes are visible in RAM.
             * 
             * Action: Flush (writeback) CPU caches to memory.
             * This ensures the device sees the latest data.
             */
            cache_flush_range(buffer, length);
            break;
            
        case DMA_FROM_DEVICE:
            /*
             * Device will write data, CPU will read.
             * We need to invalidate the cache so CPU reads from RAM.
             * 
             * Action: Invalidate CPU caches.
             * Note: We do this BEFORE DMA so that any dirty cache lines
             * are handled before device writes (on non-coherent systems).
             */
            cache_invalidate_range(buffer, length);
            break;
            
        case DMA_BIDIRECTIONAL:
            /* Must handle both cases */
            cache_flush_invalidate_range(buffer, length);
            break;
    }
    
    /* Memory barrier to ensure cache operations complete before DMA starts */
    __asm__ volatile ("mfence" ::: "memory");
}
 
/*
 * Synchronize buffer after DMA transfer (AFTER DMA completes)
 * 
 * Called after device has written data that CPU will read,
 * or after device has read data (less critical).
 */
void dma_sync_for_cpu(void *buffer, size_t length, int direction) {
    /* Memory barrier to ensure DMA writes are visible */
    __asm__ volatile ("lfence" ::: "memory");
    
    switch (direction) {
        case DMA_TO_DEVICE:
            /*
             * Device has read the data.
             * No cache action strictly required, but invalidating
             * can prevent confusion if buffer is reused.
             */
            /* Optional: cache_invalidate_range(buffer, length); */
            break;
            
        case DMA_FROM_DEVICE:
            /*
             * Device has written data, CPU needs to read.
             * CRITICAL: Ensure CPU reads from memory, not stale cache.
             * 
             * Action: Invalidate CPU caches.
             */
            cache_invalidate_range(buffer, length);
            break;
            
        case DMA_BIDIRECTIONAL:
            cache_invalidate_range(buffer, length);
            break;
    }
}
 
/*
 * Allocate DMA-coherent memory
 * 
 * Some systems provide memory that is automatically coherent
 * between CPU and DMA - no explicit cache management needed.
 * This is often slower for CPU access but simpler to use.
 */
void *dma_alloc_coherent(size_t size, uint64_t *dma_handle) {
    /* Implementation allocates uncacheable memory or
     * uses special coherent region with hardware snooping.
     * 
     * On x86: Memory is coherent by default.
     * On ARM: May use uncacheable mapping or CMA with CMO.
     */
    void *virt = alloc_pages_dma(size);
    *dma_handle = virt_to_phys(virt);
    return virt;
}
 
/*
 * Streaming DMA mapping
 * 
 * For one-shot DMA operations, streaming mappings are more
 * efficient than coherent allocations.
 */
uint64_t dma_map_single(void *buffer, size_t size, int direction) {
    /* Perform cache management for this mapping */
    dma_sync_for_device(buffer, size, direction);
    
    /* Return physical/DMA address */
    return virt_to_phys(buffer);
}
 
void dma_unmap_single(uint64_t dma_addr, size_t size, int direction) {
    void *buffer = phys_to_virt(dma_addr);
    
    /* Perform cache management for unmapping */
    dma_sync_for_cpu(buffer, size, direction);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

/*
 * NVMe DMA Flow (Simplified)
 * 
 * Demonstrates the queue-based DMA architecture of modern storage.
 */
 
#include <stdint.h>
 
/* NVMe Queue structure (simplified) */
struct nvme_queue {
    /* Submission queue - commands written by host, read by device */
    struct nvme_sqe *sq;           /* Virtual address (for CPU access) */
    uint64_t sq_dma;               /* Physical/DMA address (for device) */
    uint16_t sq_head;              /* Device has read up to here */
    uint16_t sq_tail;              /* Host has written up to here */
    
    /* Completion queue - completions written by device, read by host */
    struct nvme_cqe *cq;
    uint64_t cq_dma;
    uint16_t cq_head;              /* Host has read up to here */
    volatile uint16_t *cq_doorbell; /* MMIO doorbell register */
    volatile uint16_t *sq_doorbell;
    
    uint16_t depth;                /* Queue depth */
    uint8_t phase;                 /* Completion phase bit */
};
 
/* Submit a read command */
int nvme_submit_read(struct nvme_queue *q, uint64_t lba, 
                     uint32_t num_blocks, void *buffer, 
                     uint64_t buffer_dma) {
    /* Check queue has space */
    uint16_t next_tail = (q->sq_tail + 1) % q->depth;
    if (next_tail == q->sq_head) {
        return -1;  /* Queue full */
    }
    
    /* Build the command in the submission queue */
    struct nvme_sqe *cmd = &q->sq[q->sq_tail];
    
    cmd->opcode = 0x02;             /* Read command */
    cmd->flags = 0;
    cmd->command_id = q->sq_tail;   /* Use slot as ID */
    cmd->nsid = 1;                  /* Namespace 1 */
    cmd->prp1 = buffer_dma;         /* Physical address of data buffer */
    cmd->prp2 = 0;                  /* For multi-page, would be PRP list */
    cmd->cdw10 = lba & 0xFFFFFFFF;  /* Starting LBA (low 32 bits) */
    cmd->cdw11 = lba >> 32;         /* Starting LBA (high 32 bits) */
    cmd->cdw12 = num_blocks - 1;    /* Number of blocks (0-based) */
    
    /* Ensure command is visible in memory before ringing doorbell */
    __asm__ volatile ("sfence" ::: "memory");
    
    /* Advance tail */
    q->sq_tail = next_tail;
    
    /* Ring the doorbell - MMIO write tells device to fetch commands */
    *q->sq_doorbell = q->sq_tail;
    
    return 0;
}
 
/* Poll for completion */
struct nvme_cqe *nvme_poll_completion(struct nvme_queue *q) {
    struct nvme_cqe *cqe = &q->cq[q->cq_head];
    
    /* Check phase bit to see if this entry is new */
    /* Phase bit flips each time queue wraps around */
    if ((cqe->status & 0x01) != q->phase) {
        return NULL;  /* No new completion */
    }
    
    /* Completion is ready */
    /* Note: Device DMA'd this completion to our CQ in host memory */
    
    /* Advance head, flip phase if wrapped */
    q->cq_head++;
    if (q->cq_head >= q->depth) {
        q->cq_head = 0;
        q->phase = !q->phase;
    }
    
    /* Update completion queue doorbell */
    *q->cq_doorbell = q->cq_head;
    
    return cqe;
}
 
/*
 * Network RX Ring Example (e.g., Intel NIC)
 * 
 * Similar concept: ring of descriptors, device fills them via DMA.
 */
struct rx_descriptor {
    uint64_t buffer_addr;   /* Physical address of RX buffer */
    uint64_t header_addr;   /* Header buffer (optional) */
};
 
struct rx_completion {
    uint16_t length;        /* Packet length */
    uint16_t vlan;          /* VLAN tag */
    uint32_t rss_hash;      /* RSS hash for steering */
    uint32_t flags;         /* Checksum status, etc. */
    uint16_t status;        /* DD (descriptor done) bit */
};
 
void setup_rx_ring(void *device_base, struct rx_descriptor *ring,
                   uint64_t ring_dma, int ring_size) {
    /* Tell device where the RX descriptor ring is located */
    mmio_write64(device_base + RX_DESC_BASE, ring_dma);
    mmio_write32(device_base + RX_DESC_LEN, ring_size * sizeof(struct rx_descriptor));
    
    /* Fill ring with buffer addresses */
    for (int i = 0; i < ring_size; i++) {
        void *buffer = alloc_dma_buffer(2048);
        ring[i].buffer_addr = virt_to_phys(buffer);
    }
    
    /* Set head = 0, tail = ring_size - 1 (all descriptors available) */
    mmio_write32(device_base + RX_HEAD, 0);
    mmio_write32(device_base + RX_TAIL, ring_size - 1);
    
    /* Enable RX (device will DMA packets into our buffers) */
    mmio_write32(device_base + RX_CTRL, RX_ENABLE);
}