c - 这个速度有多危险 `strlen` ？

Question

strlen 是一个相当简单的函数，显然它的计算复杂度为 O(n)。但是，我看到了一些一次对多个字符进行操作的方法。参见示例 5 here或者这种方法 here .这些工作的基本方法是将 char const* 缓冲区重新解释转换为 uint32_t const* 缓冲区，然后一次检查四个字节。

就个人而言，我的直觉 react 是这是一个等待发生的段错误，因为我可能会在有效内存之外取消引用最多三个字节。然而，这个解决方案似乎一直存在，我觉得奇怪的是，如此明显损坏的东西经受住了时间的考验。

我认为这包括 UB 有两个原因:

1. 有效内存之外的潜在取消引用
2. 未对齐指针的潜在取消引用

(^{_{请注意，不存在别名问题；有人可能认为 uint32_t 被别名为不兼容的类型，并且代码在 strlen 之后(例如可能更改字符串的代码)可能会乱序运行到 strlen，但事实证明 char 是严格别名的显式异常(exception)}} ).

但是，在实践中失败的可能性有多大？至少，我认为在字符串文字数据部分之后需要 3 字节填充，malloc 需要 4 字节或更大对齐(实际上大多数系统都是这种情况), malloc 需要分配3 额外的字节。还有其他与别名相关的标准。这对于创建自己环境的编译器实现来说都很好，但是现代硬件上用户代码满足这些条件的频率如何？

Answer 1

该技术是有效的，如果您调用我们的 C 库 strlen，您将无法避免它。例如，如果该库是最新版本的 GNU C 库(至少在某些目标上)，它会做同样的事情。

使其工作的关键是确保指针正确对齐。如果指针对齐，则该操作肯定会读取超出字符串末尾的部分，但不会进入相邻页面。如果空终止字节在页面末尾的一个字内，则将访问最后一个字而不触及后续页面。

它在 C 中肯定不是明确定义的行为，因此当从一个编译器移植到另一个编译器时，它会承担仔细验证的负担。它还会触发 Valgrind 等越界访问检测器的误报。

Valgrind 必须修补才能绕过 Glibc 执行此操作。如果没有补丁，您会遇到如下令人讨厌的错误:

==13669== Invalid read of size 8
==13669==    at 0x411D6D7: __wcslen_sse2 (wcslen-sse2.S:59)
==13669==    by 0x806923F: length_str (lib.c:2410)
==13669==    by 0x807E61A: string_out_put_string (stream.c:997)
==13669==    by 0x8075853: obj_pprint (lib.c:7103)
==13669==    by 0x8084318: vformat (stream.c:2033)
==13669==    by 0x8081599: format (stream.c:2100)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)
==13669==  Address 0x43bcaf8 is 56 bytes inside a block of size 60 alloc'd
==13669==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==13669==    by 0x8063C4F: chk_malloc (lib.c:1763)
==13669==    by 0x806CD79: sub_str (lib.c:2653)
==13669==    by 0x804A7E2: sysroot_helper (txr.c:233)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)

Glibc 使用 SSE 指令来计算 wcslen 一次八个字节(而不是四个，wchar_t 的宽度)。这样做时，它在 60 字节宽的 block 中的偏移量 56 处进行访问。但是，请注意，此访问永远不会跨越页面边界:地址可以被 8 整除。

如果您使用的是汇编语言，则无需再考虑该技术。

事实上，该技术在我使用的一些优化音频编解码器(针对 ARM)中使用得相当多，这些编解码器在 Neon 指令集中包含大量手写汇编语言。

我在集成这些编解码器的代码上运行 Valgrind 时注意到它，并联系了供应商。他们解释说这只是一种无害的循环优化技术；我研究了汇编语言并说服自己他们是对的。