# mesi-cmodel

**Repository Path**: tugouxp/mesi-cmodel

## Basic Information

- **Project Name**: mesi-cmodel
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-04-10
- **Last Updated**: 2026-04-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# MESI Cache Coherence Protocol - Snooping Bus C Model

基于 snooping bus 的 MESI 缓存一致性协议 C 语言参考模型，协议设计参照 `ch5-4.pdf` 文档。

## 协议概述

MESI 是一种广泛应用于多处理器系统的缓存一致性协议，通过四个状态维护多个私有缓存之间的数据一致性：

| 状态 | 全称 | 含义 | 内存一致性 | 持有者数量 |
|------|------|------|-----------|-----------|
| **M** | Modified | 数据已修改（脏），仅本缓存持有 | 内存过时 | 1 (owner) |
| **E** | Exclusive | 数据干净，仅本缓存持有 | 内存最新 | 1 (owner) |
| **S** | Shared | 数据干净，多个缓存共享 | 内存最新 | >=2 |
| **I** | Invalid | 无效/不在缓存中 | - | 0 |

### MESI vs MSI 核心优势

在 MSI 协议中，读缺失后块进入 Shared 状态，后续写需要 BusUpgr 总线事务。MESI 通过区分 Exclusive（仅一个持有者且干净）和 Shared（多个持有者），使得 **E -> M 写命中不需要任何总线事务**，有效减少了总线带宽消耗。

## 状态机

### 处理器本地操作触发的转换

```
              Read Hit          Write Hit          Read Miss          Write Miss
  M -----> M (无总线事务)   M -----> M          (不可能)           (不可能)
  E -----> E (无总线事务)   E -----> M ★        I -----> E ★★     I -----> M
  S -----> S (无总线事务)   S -----> M ▲        (不可能)           (不可能)
  I -----> (不可能)         (不可能)            I -----> E/S       I -----> M

  ★  MESI核心优势：E->M 不需要总线事务
  ★★ BusRd + SHARER=0 -> E; SHARER=1 -> S
  ▲  S->M 需要 BusUpgr，使其他共享者失效
```

### 总线侦听 (Snoop) 触发的转换

非请求者缓存监听总线事务后做出反应：

```
BusRd (另一核读请求):
  M -> S  (提供数据 intervention，写回内存，置 SHARER=1)
  E -> S  (置 SHARER=1)
  S -> S  (置 SHARER=1)

BusRdX / BusUpgr (另一核请求独占权):
  M -> I  (提供数据，写回内存)
  E -> I
  S -> I
```

### 总线事务类型

| 事务 | 触发场景 | 作用 |
|------|---------|------|
| **BusRd** | 读缺失 | 请求共享副本，其他缓存置 SHARER 信号 |
| **BusRdX** | 写缺失 | 请求独占所有权，其他缓存失效 |
| **BusUpgr** | 写命中 Shared | 升级为 Modified，其他共享者失效 |
| **BusWB** | 驱逐 M 行 | 将脏数据写回内存 |

## 项目结构

```
.
├── mesi.h          # 数据结构与 API 定义
├── mesi.c          # MESI 状态机完整实现
├── test_mesi.c     # 19 个测试用例（含 1024 核可扩展性测试）
├── Makefile        # 构建系统
├── mesi_viz.html   # 协议架构可视化页面
├── SKILLS.md       # 方法论沉淀文档
├── ch5-4.pdf       # MESI 协议参考文档
└── README.md       # 本文件
```

## 编译与运行

```bash
# 使用 Makefile 编译
make

# 运行测试
make test

# 调试构建（-g -O0）
make debug

# 静态分析（需安装 clang scan-build）
make scan-build

# 清理构建产物
make clean
```

也可以手动编译：

```bash
gcc -Wall -Wextra -O2 -std=c11 -o test_mesi mesi.c test_mesi.c
./test_mesi
```

## 协议架构可视化

```bash
# 在浏览器中打开可视化页面
make viz

# 或直接打开
# firefox mesi_viz.html / open mesi_viz.html
```

可视化页面包含 8 个交互式章节：

| 章节 | 内容 |
|------|------|
| Four States | M/E/S/I 四状态卡片，含内存一致性、持有者数量、关键特性 |
| State Machine | SVG 状态转换图，分本地操作和总线侦听两类 |
| Architecture | 多核 Snooping Bus 架构图，含缓存结构和总线信号 |
| Bus Transactions | BusRd/BusRdX/BusUpgr/BusWB 事务表及侦听反应 |
| Addressing | 地址分解可视化（Tag/Index/Offset） |
| Data Flow | 三条关键数据流：Intervention / E->M Silent Upgrade / Write Invalidation |
| MESI vs MSI | 对比面板，量化 E->M 零总线事务优势 |
| Code Structure | 三文件代码结构卡片：mesi.h 数据结构 / mesi.c API / test_mesi.c 测试 |

预期输出示例：

```
============================================
  MESI Cache Coherence Protocol C Model
  Snooping Bus Implementation
============================================

>>>>>> TEST: Read miss -> Exclusive (uncached block) <<<<<<
  PASS (line 63): Core0 addr 0x0000 state=E
  PASS (line 69): Core0 addr 0x0000 state=M
  PASS: E->M transition did NOT generate bus transaction (MESI advantage)

>>>>>> TEST: Read miss -> Shared (block cached elsewhere) <<<<<<
  ...

All tests PASSED.
```

## 测试用例说明

| 测试 | 覆盖的转换 | 验证要点 |
|------|-----------|---------|
| `test_read_miss_exclusive` | I -> E, E -> M | 读缺失进入 E；写命中 E 不产生总线事务 |
| `test_shared_read` | E -> S, I -> S | 多核读同一地址，先到者 E->S，后来者进入 S |
| `test_write_hit_shared` | S -> M (BusUpgr) | 写命中 S 触发 BusUpgr，其他共享者失效 |
| `test_write_miss` | E -> M, M -> I (BusRdX) | 写缺失触发 BusRdX，前拥有者被失效 |
| `test_modified_intervention` | M -> S (intervention) | M 状态缓存收到 BusRd 时提供数据并降级为 S |
| `test_eviction_writeback` | M -> I (evict) | M 行驱逐时自动写回内存 |
| `test_data_coherence` | 跨核数据正确性 | 写后读、失效后再读，数据值始终正确 |
| `test_mesi_advantage_over_msi` | E -> M 零开销 | 量化验证 MESI 比 MSI 少一次总线事务 |
| `test_full_state_machine` | I->E->M->S->M->I->S | 完整遍历所有状态转换路径 |
| `test_multi_word_write` | 多字节写入 | cache line 内多字节写入及跨核读取 |
| `test_eviction_of_shared_line` | S/E 行驱逐 | S/E 行驱逐不触发写回 |
| `test_busrdx_intervention_not_counted` | BusRdX 语义 | M 在 BusRdX 提供数据不计为 intervention |
| `test_read_after_shared_eviction` | 内存一致性 | intervention 写回后驱逐再读数据正确 |

### 1024 核可扩展性测试

| 测试 | 验证要点 |
|------|---------|
| `test_1024_exclusive_ownership` | 1024 核各读不同地址，全部进入 Exclusive 状态 |
| `test_1024_massive_sharing` | 1024 核读同一地址，全部进入 Shared 状态 |
| `test_1024_write_invalidates_all` | 1 核写入，1023 核全部被失效 |
| `test_1024_ping_pong` | Core0 与 Core1023 交替写同一地址（20 轮） |
| `test_1024_data_integrity` | 512 核共享后失效，另 512 核再共享，数据始终正确 |
| `test_1024_private_data_isolation` | 1024 核各写私有地址，互不干扰 |
| `test_1024_aggregate_stats` | 全局统计校验：读/写/缺失/总线/失效计数精确匹配 |

## 可配置参数

在 `mesi.h` 中可修改以下宏定义：

| 宏 | 默认值 | 说明 |
|----|-------|------|
| `MESI_MAX_CORES` | 1024 | 最大处理器核数 |
| `MESI_CACHE_LINES` | 16 | 每个缓存的行数 |
| `MESI_ADDR_BITS` | 16 | 物理地址位数 |
| `MESI_LINE_SIZE` | 16 | cache line 大小（字节） |

## API 参考

### 初始化

```c
void mesi_system_init(mesi_system_t *sys, int num_cores);
```

初始化 MESI 系统，包含 `num_cores` 个处理器核，内存填充为 `addr & 0xFF` 模式。

### 处理器读

```c
int mesi_processor_read(mesi_system_t *sys, int core_id, uint32_t addr, uint8_t *out_data);
```

- **命中** (M/E/S)：直接返回数据，状态不变
- **缺失**：发出 BusRd，根据 SHARER 信号进入 E 或 S；M 状态的其他缓存会 intervention 提供数据

### 处理器写

```c
int mesi_processor_write(mesi_system_t *sys, int core_id, uint32_t addr, uint8_t *data, int len);
```

- **命中 M**：直接写入，无总线事务
- **命中 E**：直接写入并转为 M，无总线事务（MESI 优势）
- **命中 S**：发出 BusUpgr，其他共享者失效，转为 M
- **缺失**：发出 BusRdX，其他持有者失效，进入 M

### 缓存行驱逐

```c
void mesi_cache_evict(mesi_system_t *sys, int core_id, int line_idx);
```

驱逐指定缓存行。若该行处于 M 状态，自动写回内存。

### 状态输出

```c
void mesi_print_state(mesi_system_t *sys);   // 打印所有核的缓存状态
void mesi_print_stats(mesi_system_t *sys);   // 打印统计信息
```

### 统计指标

| 指标 | 说明 |
|------|------|
| `reads` / `writes` | 处理器读/写总次数 |
| `read_misses` / `write_misses` | 读/写缺失次数 |
| `writebacks` | 脏行写回次数 |
| `bus_transactions` | 总线事务发起次数 |
| `invalidations_sent` | 使其他缓存失效的次数 |
| `invalidations_recv` | 被其他核失效的次数 |
| `interventions` | 作为 M 持有者提供数据给其他核的次数 |

## 关键实现机制

### SHARER 信号线

`bus.shared_line` 在 snoop 阶段由其他缓存置位。请求者根据该信号判断读缺失后进入 E（无其他共享者）还是 S（有其他共享者）。

### Intervention（干预）

M 状态的缓存在收到 BusRd 时主动将数据放到总线上并写回内存，使请求者无需等待内存响应即可获得最新数据，同时自身降级为 S。

### 写回策略

- M 行被驱逐时自动写回内存
- M 行被 BusRdX/BusUpgr 失效时，数据通过总线转发给请求者并写回内存

## 许可

本项目仅供学习与研究使用。