ARM 裸机互斥的 Voting Locksvlocks机制算法原理与 Linux 内核 ARM 实现剖析【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux本文以 Linux 内核文档 Documentation/arch/arm/vlocks.rst 为主体结合仓库内 ARM 平台真实实现 arch/arm/common/vlock.S 与 arch/arm/common/vlock.h深入讲解 Voting Locks投票锁简称 vlocks的设计动机、选举算法、公平性与扩展性局限以及它在 ARM 多核/多簇平台如 big.LITTLE中如何被用于协调缓存尚未启用阶段的 CPU 互斥。读完本文你将掌握 vlocks 的完整工作流程、其与 Lamport 面包店算法的关联以及内核中单次 LDR 读取整块投票数组这一关键优化的底层原理并能在自己的场景中判断是否适合使用 vlocks。vlocks 是什么为什么需要一种新的自旋锁在常规的多核 Linux 系统中CPU 之间通过普通自旋锁spinlock协调临界区。但自旋锁正常工作隐含了一个前提所有参与竞争的 CPU 处于一致coherent的缓存/内存视图下。而在某些硬件平台上例如基于 ARM big.LITTLE 架构的早期启动阶段CPU 之间彼此是非缓存一致的non-coherent硬件也没有提供其他互斥原语此时普通自旋锁无法使用。vlocksVoting Locks正是为此设计的一种低层次的互斥机制它只对内存系统提出合理且最小的要求——即对单个内存位置的写操作具备原子性。它的典型使用场景是协调那些其余部分互不缓存一致的 CPU 之间的关键活动在硬件不提供其他机制、普通自旋锁又不可用的场合下使用。从当前仓库的构建脚本 arch/arm/common/Makefile 可以看到vlocks 的实现文件是随CONFIG_MCPM多簇电源管理Multi-Cluster Power Management一起编译的obj-$(CONFIG_MCPM) mcpm_head.o mcpm_entry.o mcpm_platsmp.o vlock.o也就是说vlocks 在内核中的实际消费者是 MCPM 框架——它负责在 big.LITTLE 平台上管理 CPU/簇的上电与下电。选举式互斥算法与伪代码vlocks 的基本思想非常直观让每个 CPU 投自己一票写入一个唯一编号到共享内存位置所有投票结束后内存中最终可见的那个值就是获胜者。为了确保选举在有限时间内产生无歧义的结果一个 CPU 只有在尚未选出胜者、且选举看起来还没开始时才会参与选举。文档给出了完整的伪代码这里原样继承并逐段注释int currently_voting[NR_CPUS] { 0, }; int last_vote -1; /* no votes yet */ bool vlock_trylock(int this_cpu) { /* signal our desire to vote */ currently_voting[this_cpu] 1; if (last_vote ! -1) { /* someone already volunteered himself */ currently_voting[this_cpu] 0; return false; /* not ourself */ } /* lets suggest ourself */ last_vote this_cpu; currently_voting[this_cpu] 0; /* then wait until everyone else is done voting */ for_each_cpu(i) { while (currently_voting[i] ! 0) /* wait */; } /* result */ if (last_vote this_cpu) return true; /* we won */ return false; } bool vlock_unlock(void) { last_vote -1; }算法可以拆解为四个阶段声明投票意向将自己的currently_voting[i]置 1向其他 CPU 宣告我要参与本轮选举检查是否已有胜者若last_vote ! -1说明本轮选举已经有人胜出立刻撤回意向并返回失败投出自己的票把自己写进last_vote然后清掉自己的意向标志等待选举收尾轮询所有 CPU 的currently_voting[]直到全部清零——此时last_vote中保存的值就是唯一的胜者如果获胜者恰好是自己返回 true。与 Lamport 面包店算法的关系文档明确指出currently_voting[]数组为 CPU 提供了选举是否正在进行的判定手段其角色类似于 Lamport 面包店算法中的 entering 数组参考 [1]Lamport, L. A New Solution of Dijkstras Concurrent Programming Problem, Communications of the ACM 17, 8 (August 1974), 453-455。两者在进入临界区前先声明意图这一点上异曲同工但 vlocks 有一个关键差异一旦选举开始就直接依赖底层内存系统的写原子性来挑选胜者。这样既不需要一个静态优先级规则来充当决胜者tie-breaker也不需要任何可能溢出的计数器。正确性要点文档强调只要last_vote变量对所有 CPU 全局可见那么当每个 CPU 都清除了自己的currently_voting标志之后last_vote中只会保存一个值且该值不再变化——这正是选举结果无歧义性的来源。特性与局限不公平、不扩展、可级联文档明确列出了 vlocks 的三条重要特性与限制理解它们对于判断何时该用 vlocks至关重要不保证公平not fair在竞争激烈的情况下最后一个尝试获取锁的 CPU 最有可能获胜。因此 vlocks 最适合必须挑出一个唯一胜者、但具体是哪个 CPU 获胜并不重要的场景。不适合大量 CPU与其他类似机制一样vlocks 在 CPU 数量很大时扩展性不佳。可以级联成投票层次如果确有需要可以通过把 vlocks 组织成多级投票树来改善扩展性。文档给出了一个面向 4096 个 CPU 的假想示例这里完整保留/* first level: local election */ my_town towns[(this_cpu 4) 0xf]; I_won vlock_trylock(my_town, this_cpu 0xf); if (I_won) { /* we won the town election, lets go for the state */ my_state states[(this_cpu 8) 0xf]; I_won vlock_lock(my_state, this_cpu 0xf); if (I_won) { /* and so on */ I_won vlock_lock(the_whole_country, this_cpu 0xf); if (I_won) { /* ... */ } vlock_unlock(the_whole_country); } vlock_unlock(my_state); } vlock_unlock(my_town);这个镇 → 州 → 国家的三级选举用 16×16×16 4096 的寻址把竞争拆散到不同层级的锁上先在本簇town内选出一个代表代表再去竞争上一级锁逐级向上从而把每把锁的竞争面控制在 16 个 CPU 以内。锁的获取与释放严格对称从最内层依次释放回最外层。ARM 实现从伪代码到汇编的三处关键优化文档指出当前 ARM 实现[2] 即仓库内的 arch/arm/common/vlock.S在基础算法之上做了三处优化。对照仓库源码可以逐一验证。优化一打包投票数组单次 LDR 读取将currently_voting[]的数组成员紧密打包后只要竞争同一把锁的 CPU 数量足够少整个数组可以在一次内存事务中读完从而减少访问外部内存的往返次数。在 ARM 实现中这意味着可以用一次加载加一次比较LDR Rt, [Rn] CMP Rt, #0来取代逐字节检查的等价代码LDRB Rt, [Rn] CMP Rt, #0 LDRBEQ Rt, [Rn, #1] CMPEQ Rt, #0 LDRBEQ Rt, [Rn, #2] CMPEQ Rt, #0 LDRBEQ Rt, [Rn, #3] CMPEQ Rt, #0这一优化既能降低快速路径fast-path的延迟在竞争场景下还可能减少总线争用。它依赖的事实是ARM 内存系统保证不同大小、相互重叠的内存访问之间是一致的许多其他架构也有同样的保证。值得注意的是文档特别说明由于我们并不关心currently_voting的哪个元素落在Rt的哪些位上所以这个优化完全不需要担心端序endianness问题。如果 CPU 数量多到无法一次事务读完整个数组则仍需要多次事务。此时实现使用一个简单的字长word加载循环事务次数依然远少于逐字节加载。这个优化在仓库源码中有直接对应物。arch/arm/common/vlock.h 中把投票数组的大小按字对齐#define VLOCK_OWNER_OFFSET 0 #define VLOCK_VOTING_OFFSET 4 #define VLOCK_VOTING_SIZE ((MAX_CPUS_PER_CLUSTER 3) / 4 * 4) #define VLOCK_SIZE (VLOCK_VOTING_OFFSET VLOCK_VOTING_SIZE) #define VLOCK_OWNER_NONE 0而 arch/arm/common/vlock.S 通过预处理器在少数派与多数派两条代码路径之间选择/* Select different code if voting flags can fit in a single word. */ #if VLOCK_VOTING_SIZE 4 #define FEW(x...) #define MANY(x...) x #else #define FEW(x...) x #define MANY(x...) #endif当VLOCK_VOTING_SIZE 4即整个投票标志数组能放进一个 32 位字时等待循环只用一条FEW路径的ldr r2, [r0, #VLOCK_VOTING_OFFSET]即可一次读完所有投票标志否则走MANY路径用字长步进循环逐字读取vlock.SMANY( mov r3, #VLOCK_VOTING_OFFSET ) 0: MANY( ldr r2, [r0, r3] ) FEW( ldr r2, [r0, #VLOCK_VOTING_OFFSET] ) cmp r2, #0 wfene bne 0b MANY( add r3, r3, #4 ) MANY( cmp r3, #VLOCK_VOTING_OFFSET VLOCK_VOTING_SIZE ) MANY( bne 0b )这里wfenewait for event若不等则等待在等待期间让 CPU 进入低功耗等待状态被sev唤醒从而把自旋等待变成事件驱动的休眠-唤醒进一步降低总线与功耗开销。文档也坦承原则上还可以用LDRD或LDM做更大粒度的聚合加载但为了保持代码简单初始实现没有这么做。优化二面向缓存未启用场景精简内存屏障vlocks 目前只用于协调那些尚无法启用缓存的 CPU。正因为代码运行在无缓存Strongly-Ordered 或 Device 类型内存的环境中实现可以去掉大量在缓存内存中执行该算法所必需的内存屏障barrier。这一点在源码的注释中写得非常明确vlock.SThe vlock structure must reside in Strongly-Ordered or Device memory. This implementation deliberately eliminates most of the barriers which would be required for other memory types, and assumes that independent writes to neighbouring locations within a cacheline do not interfere with one another.同时也要注意该优化的边界条件currently_voting数组的打包在缓存内存中是不成立的——除非所有竞争这把锁的 CPU 都缓存一致否则某个 CPU 的缓存写回writeback会覆盖其他 CPU 写入的值。文档还补了一句俏皮的提醒如果所有 CPU 真的缓存一致那还不如直接使用正规的自旋锁。在内核实际使用中vlocks 的锁结构被放置在 MCPM 同步结构中供MMU 和缓存都尚未使能、也没有可用栈空间的汇编启动代码调用——这正是 arch/arm/include/asm/mcpm.h 中mcpm_sync_init()的语义This prepares memory used by vlocks and the MCPM state machine used across CPUs that may have their caches active or inactive.为可能缓存启用或未启用的 CPU 准备 vlocks 与 MCPM 状态机所用的内存。优化三用 0 表示无人投票静态初始化归零伪代码中last_vote的初值是 -1而 ARM 实现改用0 表示尚无投票。这样做的好处是静态分配的 vlock 只需放进 .bss 段就会被隐式地初始化为未锁定状态无需任何显式初始化代码。但随之而来的问题是CPU ID 可能与 0 冲突。为此实现为每个 CPU 的 ID 加上一个偏移量再写入last_vote确保没有任何 CPU 会使用值 0 作为自己的身份编号。对照源码VLOCK_OWNER_NONE即 0正是这个无人持有哨兵值vlock.h而vlock_trylock中写入的是VLOCK_VOTING_OFFSET cpu即cpu 4天然避开了 0 r0: lock structure base r1: CPU ID (0-based index within cluster) ENTRY(vlock_trylock) add r1, r1, #VLOCK_VOTING_OFFSET ... ldrb r2, [r0, #VLOCK_OWNER_OFFSET] check whether lock is held cmp r2, #VLOCK_OWNER_NONE bne trylock_fail fail if so Control dependency implies strb not observable before previous ldrb. strb r1, [r0, #VLOCK_OWNER_OFFSET] submit my vote其中控制依赖control dependency的注释点出了一个微妙的正确性细节后续的strb提交投票不会在之前的ldrb检查锁是否被持有之前被其他 CPU 观察到从而保证先检查、后投票的顺序不会被硬件重排破坏。在内核中的真实用法MCPM 的簇首锁vlocks 并非理论玩具。在 arch/arm/common/mcpm_head.S 中它被用作 MCPM 框架的first man簇首锁用来在簇上电流程中仲裁哪个 CPU 负责执行簇级初始化。关键调用点mcpm_head.Smov r0, #VLOCK_SIZE mla r11, r0, r10, r11 r11 cluster first man lock mov r0, r11 mov r1, r9 cpu bl vlock_trylock implies DMB cmp r0, #0 failed to get the lock? bne mcpm_setup_wait wait for cluster setup if so ldrb r0, [r8, #MCPM_SYNC_CLUSTER_CLUSTER] cmp r0, #CLUSTER_UP cluster already up? bne mcpm_setup if not, set up the cluster Otherwise, release the first man lock and skip setup: mov r0, r11 bl vlock_unlock b mcpm_setup_complete这段代码的流程是每个上电的 CPU 先尝试vlock_trylock竞争本簇的簇首锁——获胜者成为 first man负责执行簇级电源初始化power_up_setup失败者进入mcpm_setup_wait等待簇状态变为CLUSTER_UP如果簇已经 up则拿到锁的 CPU 立即释放并跳过设置。这正体现了 vlocks 只要挑出唯一胜者、谁赢无所谓的设计定位——簇首由谁担任并不重要重要的是只能有一个 CPU 执行簇级初始化。调用处注释 implies DMB 也呼应了文档中实现通过dmb/dsb/sev保证投票可见性与唤醒的细节见 vlock.S 的voting_begin/voting_end宏。小结与使用建议维度vlocks 的特性适用场景非缓存一致的 CPU 之间、硬件无其他互斥原语、普通自旋锁不可用底层依赖内存系统对单地址写的原子性公平性不公平后到者更可能赢适合只求唯一胜者扩展性不佳可通过多级投票树级联改善内存要求锁结构须位于 Strongly-Ordered / Device 内存初始化0 表示无人持有放 .bss 即隐式解锁内核消费方MCPMCONFIG_MCPM用作簇首first man选举锁如果你需要在一组缓存尚未启用、彼此非一致的 CPU 之间仲裁唯一胜者vlocks 是一个经过内核实战检验、且实现极其精简vlock.S 全文不足百行汇编的答案而如果你面对的是缓存一致的常规多核环境那么文档的建议依然成立——请直接使用正规的自旋锁。附注本算法最初由 Dave Martin 为 Linaro Limited 编写并记录用于 ARM big.LITTLE 平台Nicolas Pitre 与 Achin Gupta 参与了评审并提供输入文档版权归 Linaro Limited2012–2013以 GPL v2 许可发布见 COPYING。深入阅读可继续参考仓库内的 Documentation/arch/arm/vlocks.rst、arch/arm/common/vlock.h 及其调用方 arch/arm/common/mcpm_head.S。【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考