FreeBSD 的 strlen(3)

• 本文约1862字,阅读大致需要4分钟 • Kernel

之前只有一篇关于较早版本的strlen(3) 实现的笔记,这里补上我在2010年做的新增改进。

背景与历史

与Pascal等语言不同,C语言的字符串并不显式保存长度,而是在字符串末尾以NUL字符('\0')标记结束。这个设计决策是上世纪60年代做出的,坊间传闻是为了节省几个字节的存储空间,不过我个人认为也可能是因为早期汇编指令中充满了测试零值的操作。无论缘由如何,这一设计直接导致strlen必须遍历整个字符串,成为一个O(n)O(n)操作。

早期的BSD Unix采用的strlen实现十分简单粗暴,即通过循环逐字节比较是否为NUL。1993年,J.T. Conklin为i386架构撰写了汇编优化版本,其核心利用了rep scasb指令,在算法逻辑上与C版本逐字节扫描并无二致(彼时C编译器尚无法自动生成这类指令)。

为了配合x86_64平台,后来又引入了新的汇编版本。该版本的核心思想升级为按机器字(word)匹配:先以字为单位快速推进,定位到包含NUL字符的字之后,再在该字内部按原始逐字节算法精确定位NUL的位置。

我在2009年根据这个x86_64汇编思路重写了一个纯C语言版本,并在2010年完成了最终调整,形成了当前版本。算法整体流程如下:

  • 首字检测:判断首个机器字中是否存在NUL;若存在,则自起始有效位置扫描查找其中的NUL字符;
  • 按字遍历:按机器字宽度主循环扫描剩余字符串,一旦发现当前字包含NUL,则精确定位并返回总长度。

单字内零字节检测原理

整个算法中最核心、也最难理解的部分,在于如何在不拆分字节的前提下,通过纯位运算判定一个字(32位或64位整数)中是否包含零字节(NUL)。具体方法是计算两个中间变量:

  • a = (x - 0x01010101)
  • b = (~x & 0x80808080)
  • 判定 (a & b) != 0

这里的0x01010101和0x80808080在64位系统下可以相应扩展为64位的对应常数。

原理拆解如下:

第一步,对于任意一个字节:

  • 若该字节在0x01到0x7f之间,减去1后其值仍在0x00到0x7e之间,最高位(MSB)必定为0;
  • 若该字节本身为0x00,减去1后发生下溢借位,变为0xff,最高位变为1;
  • 若该字节在0x81到0xff之间,减去1后的结果仍大于等于0x80,最高位保持为1;
  • 若该字节恰好为0x80,减去1得到0x7f,最高位变为0(但这对后续判断并不产生负面影响)。

注意到,此处任何一个字节的最高位是1,必然是前面两种情况之一:要么这个字节原本就是0,要么它>= 0x81。

如果不考虑后一种情况,我们直接把减法结果& 0x80808080即可;然而,由于需要排除后一种情况的干扰,我们接着计算~x & 0x80808080。若某一字节原本>= 0x80,其最高位为1,取反后其最高位变为0;只有原本最高位为0的字节,取反后最高位才会是1。

最后将两个结果做逻辑与(a & b):若结果非0,则说明至少有一个字节是NUL。

这个位运算过程(SWAR,SIMD Within A Register)说起来复杂,但事实上计算机计算这些要比逐个字节去判断是否为0快得多。这主要得益于以下几方面:

  • 充分利用字长:直接按字长操作,免去CPU频繁处理单字节的额外开销;
  • 指令级并行(ILP):前两步计算(分别计算a和b)互不依赖,现代超标量处理器可以并发执行;
  • 极低延迟:最后一步操作直接在寄存器之间进行快速的按位与,并做单次零值判断。

内存对齐与页面安全保障

在实际工程实现中,还有一些其他技巧:

第一个技巧是,从第一个小节开始就使用字长的操作。一般来说,内存分配器在分配内存时是以字边界对齐的,因此通常传给strlen()的指针都是对齐的。不过,即使未对齐,将指针向下退到所属的整字边界(例如字长为8,指针为0x9,则退回0x8)开始读取的一个整字,也必然处于同一个内存页内,因此该访问绝不会引发缺页或内存越界异常。如果在这个整字中发现了NUL字符,只需从指针实际起始位置扫描到该整字结尾,即可确认是否真的到达了字符串末尾。同时,由于该整字已被加载到处理器缓存中,后续循环处理极快。

第二个技巧与此类似,主循环全程使用整字操作。由于整字的起始地址在内存页中,其终止地址也必然在同一个内存页中,这一访问同样不会发生意外越界(尽管在内存分配时可能出现诸如只分配了4个字节却访问了8个字节的情况,但只要不跨越页边界,硬件就不会产生异常)。换言之,如果程序原先的字符串访问不会越界异常,优化后的整字读取也绝不会发生越界异常。

源码参考

优化后的strlen源码可在FreeBSD官方源码库lib/libc/string/strlen.c中查阅。