3.4 BMCA算法实现：民主选举的代码艺术
从协议到代码
第二章我们详细讲解了BMCA（最佳主时钟算法）的原理。
现在，让我们看看这个算法在LinuxPTP中是如何实现的。
BMCA的核心函数
LinuxPTP的BMCA实现集中在bmc.c文件中，只有175行代码。
核心函数列表
bmc.c提供的函数：
1. dscmp(struct dataset *a, struct dataset *b)
- 比较两个数据集，决定哪个更适合当主时钟
2. dscmp2(struct dataset *a, struct dataset *b)
- 第二阶段比较（当clockIdentity相同时）
3. portid_cmp(struct PortIdentity *a, struct PortIdentity *b)
- 比较两个端口标识
4. bmc_state_decision(struct clock *c, struct port *r, ...)
- 根据BMCA结果决定端口状态
数据集比较函数详解
portid_cmp：端口标识比较
/* bmc.c, 第24-33行 */
static int portid_cmp(struct PortIdentity *a, struct PortIdentity *b)
{
int diff = memcmp(&a->clockIdentity, &b->clockIdentity,
sizeof(a->clockIdentity));
if (diff == 0) {
diff = a->portNumber - b->portNumber;
}
return diff;
}
返回值含义：
diff < 0：a < b（a排在前面）
diff = 0：a = b（完全相同）
diff > 0：a > b（b排在前面）
比较顺序：
先比较clockIdentity（8字节）：
- 如果不同，直接返回比较结果
如果clockIdentity相同，再比较portNumber（2字节）：
- 返回端口号的差异
这意味着：
- 同一设备的两个端口，用端口号区分
- 不同设备的端口，用clockIdentity区分
dscmp：主比较函数
/* bmc.c, 第83-127行 */
int dscmp(struct dataset *a, struct dataset *b)
{
int diff;
/* 特殊情况：同一数据集 */
if (a == b)
return 0;
/* 特殊情况：其中一个为空 */
if (a && !b)
return A_BETTER;
if (b && !a)
return B_BETTER;
/* 比较clockIdentity */
diff = memcmp(&a->identity, &b->identity, sizeof(a->identity));
if (!diff)
return dscmp2(a, b); /* 相同，进入第二阶段 */
/* 比较priority1 */
if (a->priority1 < b->priority1)
return A_BETTER;
if (a->priority1 > b->priority1)
return B_BETTER;
/* 比较clockClass */
if (a->quality.clockClass < b->quality.clockClass)
return A_BETTER;
if (a->quality.clockClass > b->quality.clockClass)
return B_BETTER;
/* 比较clockAccuracy */
if (a->quality.clockAccuracy < b->quality.clockAccuracy)
return A_BETTER;
if (a->quality.clockAccuracy > b->quality.clockAccuracy)
return B_BETTER;
/* 比较offsetScaledLogVariance */
if (a->quality.offsetScaledLogVariance <
b->quality.offsetScaledLogVariance)
return A_BETTER;
if (a->quality.offsetScaledLogVariance >
b->quality.offsetScaledLogVariance)
return B_BETTER;
/* 比较priority2 */
if (a->priority2 < b->priority2)
return A_BETTER;
if (a->priority2 > b->priority2)
return B_BETTER;
/* 比较clockIdentity */
return diff < 0 ? A_BETTER : B_BETTER;
}
返回值定义：
/* bmc.h */
#define A_BETTER 1 /* A更好，选择A */
#define B_BETTER -1 /* B更好，选择B */
#define A_BETTER_TOPO 2 /* A更好（拓扑原因） */
#define B_BETTER_TOPO -2 /* B更好（拓扑原因） */
比较流程图：
dscmp比较流程（IEEE 1588-2019标准）：
┌────────────────────────────────────────┐
│ 0. 检查特殊情况 │
│ - 同一数据集 → 0 │
│ - 一个为空 → 选择非空的 │
├────────────────────────────────────────┤
│ 1. 比较clockIdentity │
│ - 相同 → 调用dscmp2 │
│ - 不同 → 记录差异，继续 │
├────────────────────────────────────────┤
│ 2. 比较priority1 │
│ - A小 → A_BETTER │
│ - B小 → B_BETTER │
│ - 相同 → 继续 │
├────────────────────────────────────────┤
│ 3. 比较clockClass │
│ - A小 → A_BETTER │
│ - B小 → B_BETTER │
│ - 相同 → 继续 │
├────────────────────────────────────────┤
│ 4. 比较clockAccuracy │
│ - A小 → A_BETTER │
│ - B小 → B_BETTER │
│ - 相同 → 继续 │
├────────────────────────────────────────┤
│ 5. 比较offsetScaledLogVariance │
│ - A小 → A_BETTER │
│ - B小 → B_BETTER │
│ - 相同 → 继续 │
├────────────────────────────────────────┤
│ 6. 比较priority2 │
│ - A小 → A_BETTER │
│ - B小 → B_BETTER │
│ - 相同 → 继续 │
├────────────────────────────────────────┤
│ 7. 比较clockIdentity（使用之前记录的差异）│
│ - A小 → A_BETTER │
│ - B大 → B_BETTER │
└────────────────────────────────────────┘
关键点：
为什么先检查clockIdentity？
diff = memcmp(&a->identity, &b->identity, sizeof(a->identity));
if (!diff)
return dscmp2(a, b);
如果两个数据集的clockIdentity相同：
- 它们来自同一个设备
- 需要用dscmp2进行拓扑比较
- 判断哪个路径更短
如果clockIdentity不同：
- 它们来自不同设备
- 继续比较priority1等属性
- 最后用clockIdentity打破平局
dscmp2：拓扑比较函数
/* bmc.c, 第35-81行 */
int dscmp2(struct dataset *a, struct dataset *b)
{
int diff;
unsigned int A = a->stepsRemoved, B = b->stepsRemoved;
/* 情况1：stepsRemoved差距大于1 */
if (A + 1 < B)
return A_BETTER; /* A的跳数明显少 */
if (B + 1 < A)
return B_BETTER; /* B的跳数明显少 */
/* 情况2：A的跳数少1 */
if (A < B) {
diff = portid_cmp(&b->receiver, &b->sender);
if (diff < 0)
return A_BETTER;
if (diff > 0)
return A_BETTER_TOPO;
return 0; /* error-1 */
}
/* 情况3：B的跳数少1 */
if (A > B) {
diff = portid_cmp(&a->receiver, &a->sender);
if (diff < 0)
return B_BETTER;
if (diff > 0)
return B_BETTER_TOPO;
return 0; /* error-1 */
}
/* 情况4：跳数相同，比较sender */
diff = portid_cmp(&a->sender, &b->sender);
if (diff < 0)
return A_BETTER_TOPO;
if (diff > 0)
return B_BETTER_TOPO;
/* 情况5：比较receiver端口号 */
if (a->receiver.portNumber < b->receiver.portNumber)
return A_BETTER_TOPO;
if (a->receiver.portNumber > b->receiver.portNumber)
return B_BETTER_TOPO;
/* error-2 */
return 0;
}
拓扑比较的逻辑：
场景：同一设备的多个Announce报文（clockIdentity相同）
为什么要进行拓扑比较？
因为：
- 同一设备可能通过不同路径发送Announce
- 有些路径更短（stepsRemoved更小）
- 需要选择最短路径
步骤1：比较stepsRemoved
- 如果差距大于1，选择跳数少的
- 如果差距小于等于1，需要进一步分析
步骤2：分析拓扑关系
- 检查receiver和sender的关系
- 判断是否存在环路
步骤3：比较sender和receiver
- 选择端口号小的
- 确保决策一致性
图解dscmp2：
场景一：stepsRemoved差距大
网络拓扑：
主时钟 → BC1 → BC2 → 端口A（stepsRemoved = 3）
主时钟 → BC3 → 端口B（stepsRemoved = 2）
比较：
A的stepsRemoved = 3
B的stepsRemoved = 2
判断：
B + 1 = 3 = A
不满足"A + 1 < B"
但满足"B < A"
结果：B_BETTER（B更接近主时钟）
场景二：stepsRemoved差距小
网络拓扑：
主时钟 → BC1 → 端口A（stepsRemoved = 2）
主时钟 → BC2 → 端口A（stepsRemoved = 1）
两个Announce来自同一个端口A，但stepsRemoved不同。
如果stepsRemoved差1：
- 检查拓扑关系
- 判断哪个路径更合理
状态决策函数
bmc_state_decision函数
/* bmc.c, 第129-175行 */
enum port_state bmc_state_decision(struct clock *c, struct port *r,
int (*compare)(struct dataset *a,
struct dataset *b))
{
struct dataset *clock_ds, *clock_best, *port_best;
enum port_state ps;
clock_ds = clock_default_ds(c); /* 本时钟的数据集 */
clock_best = clock_best_foreign(c); /* 全局最佳外部时钟 */
port_best = port_best_foreign(r); /* 本端口最佳外部时钟 */
ps = port_state(r); /* 当前端口状态 */
/* 特殊情况：BMCA_NOOP模式 */
if (!port_best && port_bmca(r) == BMCA_NOOP) {
return ps;
}
/* 特殊情况：LISTENING状态没有外部时钟 */
if (!port_best && PS_LISTENING == ps)
return ps;
/* 规则M1/P1：clockClass <= 127 */
if (clock_class(c) <= 127) {
if (compare(clock_ds, port_best) > 0) {
return PS_GRAND_MASTER; /* M1 */
} else {
return PS_PASSIVE; /* P1 */
}
}
/* 规则M2：本时钟比全局最佳更好 */
if (compare(clock_ds, clock_best) > 0) {
return PS_GRAND_MASTER; /* M2 */
}
/* 规则S1：本端口是最佳端口 */
if (clock_best_port(c) == r) {
return PS_SLAVE; /* S1 */
}
/* 规则P2/M3：比较全局最佳和端口最佳 */
if (compare(clock_best, port_best) == A_BETTER_TOPO) {
return PS_PASSIVE; /* P2 */
} else {
return PS_MASTER; /* M3 */
}
}
IEEE 1588标准的状态决策规则：
规则M1：
- 本时钟的clockClass <= 127
- 本时钟比端口最佳外部时钟更好
- 结果：成为Grand Master
规则P1：
- 本时钟的clockClass <= 127
- 本时钟不如端口最佳外部时钟
- 结果：Passive（避免环路）
规则M2：
- 本时钟比全局最佳外部时钟更好
- 结果：成为Grand Master
规则S1：
- 本端口是全局最佳外部时钟的来源
- 结果：成为Slave
规则P2：
- 全局最佳比端口最佳拓扑更好
- 结果：Passive（环路避免）
规则M3：
- 其他情况
- 结果：成为Master
状态决策流程图
bmc_state_decision流程：
┌──────────────────────────────────────────────────────────┐
│ 开始 │
└──────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────┐
│ port_best为空 且 BMCA_NOOP？ │
│ → 是：保持当前状态 │
└──────────────────────────────────────────────────────────┘
│ 否
▼
┌──────────────────────────────────────────────────────────┐
│ port_best为空 且 LISTENING？ │
│ → 是：保持LISTENING │
└──────────────────────────────────────────────────────────┘
│ 否
▼
┌──────────────────────────────────────────────────────────┐
│ clockClass <= 127？ │
│ → 是： │
│ compare(clock_ds, port_best) > 0？ │
│ → 是：PS_GRAND_MASTER (M1) │
│ → 否：PS_PASSIVE (P1) │
└──────────────────────────────────────────────────────────┘
│ 否
▼
┌──────────────────────────────────────────────────────────┐
│ compare(clock_ds, clock_best) > 0？ │
│ → 是：PS_GRAND_MASTER (M2) │
└──────────────────────────────────────────────────────────┘
│ 否
▼
┌──────────────────────────────────────────────────────────┐
│ clock_best_port(c) == r？ │
│ → 是：PS_SLAVE (S1) │
└──────────────────────────────────────────────────────────┘
│ 否
▼
┌──────────────────────────────────────────────────────────┐
│ compare(clock_best, port_best) == A_BETTER_TOPO？ │
│ → 是：PS_PASSIVE (P2) │
│ → 否：PS_MASTER (M3) │
└──────────────────────────────────────────────────────────┘
外部时钟管理
foreign_clock结构
/* foreign.h */
struct foreign_clock {
struct port *port; /* 所属端口 */
struct PortIdentity identity; /* 外部时钟标识 */
struct dataset dataset; /* 外部时钟数据集 */
/* Announce报文队列 */
LIST_ENTRY(foreign_clock) list;
};
端口的外部时钟列表
/* port_private.h */
struct port {
/* ... */
struct foreign_clock *best; /* 最佳外部时钟 */
LIST_HEAD(foreign_clocks, foreign_clock) foreign; /* 外部时钟列表 */
/* ... */
};
外部时钟管理函数
/* foreign.c中的核心函数（简化） */
/* 添加外部时钟Announce */
struct foreign_clock *foreign_add(struct port *p, struct ptp_message *msg)
{
struct foreign_clock *fc;
/* 分配内存 */
fc = calloc(1, sizeof(*fc));
/* 初始化 */
fc->port = p;
fc->identity = msg->announce.hdr.sourcePortIdentity;
/* 添加到列表 */
LIST_INSERT_HEAD(&p->foreign, fc, list);
return fc;
}
/* 查找外部时钟 */
struct foreign_clock *foreign_lookup(struct port *p,
struct PortIdentity *identity)
{
struct foreign_clock *fc;
LIST_FOREACH(fc, &p->foreign, list) {
if (pid_eq(&fc->identity, identity))
return fc;
}
return NULL;
}
/* 更新外部时钟 */
void foreign_update(struct foreign_clock *fc, struct ptp_message *msg)
{
/* 更新数据集 */
fc->dataset.priority1 = msg->announce.grandmasterPriority1;
fc->dataset.quality = msg->announce.grandmasterClockQuality;
/* ... */
}
计算最佳外部时钟
/* port.c中的port_compute_best（简化） */
struct foreign_clock *port_compute_best(struct port *p)
{
struct foreign_clock *fc, *best = NULL;
int (*compare)(struct dataset *a, struct dataset *b);
compare = clock_dscmp(p->clock);
/* 遍历所有外部时钟 */
LIST_FOREACH(fc, &p->foreign, list) {
if (!best || compare(&fc->dataset, &best->dataset) > 0) {
best = fc;
}
}
p->best = best;
return best;
}
BMCA的完整流程
1. Announce报文接收
/* port.c中的Announce处理（简化） */
static int port_rx_announce(struct port *p, struct ptp_message *msg)
{
struct foreign_clock *fc;
/* 步骤1：查找或创建外部时钟 */
fc = foreign_lookup(p, &msg->hdr.sourcePortIdentity);
if (!fc) {
fc = foreign_add(p, msg);
}
/* 步骤2：更新外部时钟信息 */
foreign_update(fc, msg);
/* 步骤3：重启Announce超时定时器 */
timer_restart(&p->timers[ANNOUNCE_TIMER]);
/* 步骤4：触发状态决策事件 */
port_dispatch(p, EV_STATE_DECISION_EVENT, 0);
return 0;
}
2. 状态决策事件处理
/* port.c中的状态决策事件处理（简化） */
static void port_state_decision(struct port *p)
{
struct foreign_clock *best;
enum port_state next;
int mdiff = 0;
/* 步骤1：计算最佳外部时钟 */
best = port_compute_best(p);
/* 步骤2：检查主时钟是否变化 */
if (best && p->best &&
!pid_eq(&best->identity, &p->best->identity)) {
mdiff = 1; /* 主时钟变了 */
}
/* 步骤3：执行BMCA状态决策 */
next = bmc_state_decision(p->clock, p, clock_dscmp(p->clock));
/* 步骤4：转换为事件 */
enum fsm_event event = state_to_event(next);
/* 步骤5：触发状态机 */
port_dispatch(p, event, mdiff);
}
3. 状态到事件转换
/* port.c中的状态到事件转换（简化） */
static enum fsm_event state_to_event(enum port_state next)
{
switch (next) {
case PS_GRAND_MASTER:
return EV_RS_GRAND_MASTER;
case PS_MASTER:
return EV_RS_MASTER;
case PS_SLAVE:
return EV_RS_SLAVE;
case PS_PASSIVE:
return EV_RS_PASSIVE;
default:
return EV_NONE;
}
}
BMCA时序图
时间轴上的BMCA过程：
t=0: 端口启动
│
▼
t=1: 进入INITIALIZING状态
│
▼
t=2: 初始化完成，进入LISTENING状态
│
│ 启动Announce超时定时器
│
▼
t=3: 收到Announce报文（来自外部时钟A）
│
│ 创建foreign_clock结构
│ 更新外部时钟信息
│ 重启Announce超时定时器
│
▼
t=4: 计算最佳外部时钟
│
│ 比较本时钟与外部时钟A
│ 决定状态（假设本时钟更好）
│
▼
t=5: 进入PRE_MASTER状态
│
│ 启动资格超时定时器
│
▼
t=6: 资格超时
│
▼
t=7: 进入MASTER/GRAND_MASTER状态
│
│ 开始发送Announce
│ 开始发送Sync
│
假设t=10收到更好的外部时钟：
t=10: 收到Announce报文（来自外部时钟B）
│
│ B的priority1 < 本时钟的priority1
│
▼
t=11: 状态决策：B更好
│
▼
t=12: 进入UNCALIBRATED状态
│
│ 停止发送Announce
│ 开始同步到B
│
▼
t=13: 同步完成
│
▼
t=14: 进入SLAVE状态
小结：BMCA的代码智慧
分层设计：
- 数据集比较（dscmp/dscmp2）
- 状态决策（bmc_state_decision）
- 外部时钟管理（foreign_clock）
函数式编程：
- 比较函数作为参数传递
- 无副作用，易测试
标准映射：
- 代码逻辑与IEEE 1588规则一一对应
- 注释标注规则编号（M1、P1、S1等）
效率优化：
- 快速路径处理
- 避免不必要的比较
下集预告
BMCA决定谁当主时钟，伺服控制器决定如何调整时钟。
下一节，我们将分析伺服控制器实现——看看LinuxPTP如何实现PI控制器。
【悬念留给3.5】
时钟同步需要伺服控制器。
LinuxPTP实现了多种伺服：
- PI控制器（最常用）
- 线性回归滤波器
- 空滤波器
其中PI控制器只有231行代码，却实现了：
- 频率估计
- 相位调整
- 阶跃检测
它是如何工作的？
下一节，我们详细解读伺服控制器。