c - 在 x86 和 x64 上的同一页面内读取缓冲区的末尾是否安全？

Question

如果允许高性能算法中的许多方法在输入缓冲区末尾之后读取少量数据，它们就可以(并且已经)被简化。在这里，“少量”通常意味着最多 W - 1 字节超过末尾，其中 W 是算法的字节大小(例如，对于以 64 位块处理输入的算法，最多 7 个字节)。
很明显，写入超过输入缓冲区的末尾永远是不安全的，一般来说，因为您可能会破坏缓冲区1之外的数据。很明显，越过缓冲区的末尾读取到另一个页面可能会触发段错误/访问冲突，因为下一页可能无法读取。
然而，在读取对齐值的特殊情况下，页面错误似乎是不可能的，至少在 x86 上是这样。在该平台上，页面(以及内存保护标志)具有 4K 粒度(更大的页面，例如 2MiB 或 1GiB，是可能的，但这些是 4K 的倍数)，因此对齐读取将仅访问与有效页面相同的页面中的字节缓冲区的一部分。
这是一些循环的规范示例，该循环对齐其输入并读取超过缓冲区末尾的 7 个字节:

int processBytes(uint8_t *input, size_t size) {

    uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
    int res;

    if (size < 8) {
        // special case for short inputs that we aren't concerned with here
        return shortMethod();
    }

    // check the first 8 bytes
    if ((res = match(*input)) >= 0) {
        return input + res;
    }

    // align pointer to the next 8-byte boundary
    input64 = (ptrdiff_t)(input64 + 1) & ~0x7;

    for (; input64 < end64; input64++) {
        if ((res = match(*input64)) > 0) {
            return input + res < input + size ? input + res : -1;
        }
    }

    return -1;
}

内部函数 int match(uint64_t bytes) 未显示，但它会查找与特定模式匹配的字节，如果找到则返回最低的此类位置 (0-7)，否则返回 -1。
首先，为简单起见，大小 < 8 的案例被典当给另一个函数。然后对前 8 个(未对齐的字节)进行一次检查。然后对剩余的 floor((size - 7) / 8) 个 8 字节的块进行循环2。此循环最多可以读取缓冲区末尾之后的 7 个字节(7 字节情况发生在 input & 0xF == 1 时)。然而，返回调用有一个检查，它排除在缓冲区末尾之外发生的任何虚假匹配。
实际上，这样的函数在 x86 和 x86-64 上安全吗？
这些类型的重读在高性能代码中很常见。避免这种过度读取的特殊尾码也很常见。有时您会看到后一种类型取代前一种，从而使 valgrind 等工具静音。有时，您会看到进行此类替换的建议，但会以习语安全且工具有误(或过于保守)3 为由拒绝。
给语言律师的注意事项:

Reading from a pointer beyond its allocated size is definitely not allowedin the standard. I appreciate language lawyer answers, and even occasionally writethem myself, and I'll even be happy when someone digs up the chapterand verse which shows the code above is undefined behavior and hencenot safe in the strictest sense (and I'll copy the details here). Ultimately though, that's not whatI'm after. As a practical matter, many common idioms involving pointerconversion, structure access though such pointers and so aretechnically undefined, but are widespread in high quality and highperformance code. Often there is no alternative, or the alternativeruns at half speed or less.

If you wish, consider a modified version of this question, which is:

After the above code has been compiled to x86/x86-64 assembly, and the user has verified that it is compiled in the expected way (i.e.,the compiler hasn't used a provable partially out-of-bounds access todo something reallyclever,is executing the compiled program safe?

In that respect, this question is both a C question and a x86 assembly question. Most of the code using this trick that I've seen is written in C, and C is still the dominant language for high performance libraries, easily eclipsing lower level stuff like asm, and higher level stuff like <everything else>. At least outside of the hardcore numerical niche where FORTRAN still plays ball. So I'm interested in the C-compiler-and-below view of the question, which is why I didn't formulate it as a pure x86 assembly question.

All that said, while I am only moderately interested in a link to thestandard showing this is UD, I am very interested in any details ofactual implementations that can use this particular UD to produceunexpected code. Now I don't think this can happen without some deeppretty deep cross-procedure analysis, but the gcc overflow stuffsurprised a lot of people too...

1 即使在明显无害的情况下，例如，在写回相同值的情况下，它也可以是 break concurrent code 。
2 注意此重叠工作需要此函数和 match() 函数以特定的幂等方式运行 - 特别是返回值支持重叠检查。因此“查找第一个字节匹配模式”有效，因为所有 match() 调用仍然是有序的。但是，“计数字节匹配模式”方法不起作用，因为某些字节可能会被重复计算。顺便说一句:即使没有按顺序限制，某些函数(例如“返回最小字节”调用)也可以工作，但需要检查所有字节。
3 这里值得注意的是，对于 valgrind 的 Memcheck there is a flag 、 --partial-loads-ok ，它控制此类读取实际上是否报告为错误。默认值为 yes，这意味着通常不会将此类加载视为立即错误，但会努力跟踪加载字节的后续使用，其中一些有效，一些无效，并标记错误如果使用了超出范围的字节。在上述示例中，在 match() 中访问整个字的情况下，即使结果最终被丢弃，这种分析也会得出访问字节的结论。 Valgrind cannot in general 确定是否实际使用了部分加载中的无效字节(并且通常检测可能非常困难)。

Answer 1

是的，它在 x86 asm 中是安全的，并且 现有的 libc strlen(3) 实现在手写 asm 中利用了这一点。 甚至 glibc's fallback C ，但它在没有 LTO 的情况下编译，因此它永远无法内联。它基本上是使用 C 作为便携式汇编程序来为一个函数创建机器代码，而不是作为具有内联的更大 C 程序的一部分。但这主要是因为它也有潜在的严格别名 UB，请参阅我在链接问答中的回答。您可能还需要一个 GNU C __attribute__((may_alias)) typedef 而不是普通的 unsigned long 作为更宽的类型，例如 0x2313 已经使用 0x2313 等。
这是安全的，因为 对齐的加载永远不会跨越更高的对齐边界 ，并且内存保护发生在对齐的页面上，因此至少有 4k 边界1
任何触及至少 1 个有效字节的自然对齐加载都不会出错。 检查您是否离下一页边界足够远以执行 16 字节加载也是安全的，例如 __m128i 。有关更多详细信息，请参阅以下部分。

据我所知，在为 x86 编译的 C 中通常也是安全的。在对象外读取当然是 C 中的未定义行为，但在 C-targeting-x86 中有效。我不认为编译器明确/故意定义行为，但实际上它是这样工作的。
我认为这不是激进的编译器会 assume can't happen while optimizing 的那种UB，但是编译器编写者在这一点上的确认会很好，特别是对于在编译时很容易证明访问结束的情况目的。 (请参阅@RossRidge 评论中的讨论:此答案的先前版本断言它绝对安全，但 LLVM 博客文章并没有真正以这种方式阅读)。
这在 asm 中是必需的，以便一次处理一个隐式长度的字符串快于 1 个字节。在 C 中，理论上编译器可以知道如何优化这样的循环，但实际上他们不知道，所以你必须做这样的 hack。在此更改之前，我怀疑人们关心的编译器通常会避免破坏包含此潜在 UB 的代码。
当知道对象有多长的代码看不到重读时，就不会有危险。编译器必须使 asm 适用于我们实际读取的数组元素的情况。 我可以看到的可能的 future 编译器的似是而非的危险是: 内联后，编译器可能会看到 UB 并决定绝不能采用这条执行路径。或者必须在最终非完整 vector 之前找到终止条件，并在完全展开时将其排除。

你得到的数据是不可预测的垃圾，但不会有任何其他潜在的副作用。只要您的程序不受垃圾字节的影响，就可以了。 (例如，使用 bithacks to find if one of the bytes of a if (p & 4095 > (4096 - 16)) do_special_case_fallback are zero ，然后使用字节循环来查找第一个零字节，无论超出它的垃圾是什么。)

这在 x86 asm 中不安全的异常情况

Hardware data breakpoints (watchpoints) 在从给定地址加载时触发。如果您在数组之后立即监视变量，则可能会出现虚假命中。对于调试正常程序的人来说，这可能是一个小烦恼。如果您的函数将成为使用 x86 调试寄存器 D0-D3 以及可能影响正确性的结果异常的程序的一部分，那么请注意这一点。
或者类似地，像 valgrind 这样的代码检查器可能会提示在对象之外读取。

在假设的 16 位或 32 位操作系统下可以使用分段: 段限制 可以使用 4k or 1-byte granularity 可以使用 0x25181221334114 的第一个偏移量，因此它可能是奇数段。 (除了性能之外，将段的基址与缓存行或页面对齐是无关紧要的)。 所有主流 x86 操作系统都使用平面内存模型 ，x86-64 取消了对 64 位模式的段限制的支持。

紧接在缓冲区 之后的内存映射 I/O 寄存器，您希望以宽负载循环，尤其是相同的 64B 缓存行。即使您从设备驱动程序(或像 X 服务器这样映射了一些 MMIO 空间的用户空间程序)调用这样的函数，这也是极不可能的。

如果您正在处理一个 60 字节的缓冲区并且需要避免从 4 字节的 MMIO 寄存器中读取数据，那么您将了解它并将使用 uint64_t 。这种情况不会发生在普通代码中。

volatile T* 是循环的典型示例 ，该循环处理隐式长度缓冲区，因此无法在不读取缓冲区末尾的情况下进行矢量化。如果您需要避免读取超过终止的 strlen 字节，则一次只能读取一个字节。
例如，glibc 的实现使用序言来处理直到第一个 64B 对齐边界的数据。然后在主循环 (gitweb link to the asm source) 中，它使用四个 SSE2 对齐加载加载整个 64B 缓存线。它将它们合并为一个具有 0 (最小无符号字节)的 vector ，因此只有当四个 vector 中的任何一个具有零时，最终 vector 才会具有零元素。在发现字符串的末尾在该缓存行中的某个位置后，它会分别重新检查四个 vector 中的每一个以查看位置。 (使用典型的 pminub 对全零 vector 和 pcmpeqb/ pmovmskb 来查找 vector 中的位置。)glibc 曾经有几个不同的 0x25236412 上的 CPU
通常像这样的循环避免触及任何他们不需要触及的额外缓存行，而不仅仅是页面，出于性能原因，比如 glibc 的 strlen。
一次加载 64B 当然只能从 64B 对齐的指针安全，因为自然对齐的访问不能跨越 strlen strategies to choose from 。

如果您提前知道缓冲区的长度，则可以通过使用在缓冲区最后一个字节处结束的未对齐加载来处理超出最后一个完全对齐 vector 的字节，从而避免读取越过末尾。
(同样，这仅适用于幂等算法，例如 memcpy，它们不关心它们是否将存储重叠到目的地。就地修改算法通常无法做到这一点，除了像 cache-line or page-line boundaries 这样的东西，在那里可以重新处理已经被放大的数据。除了存储转发停顿，如果您执行与上次对齐的存储重叠的未对齐加载。)
因此，如果您在已知长度的缓冲区上进行矢量化，通常最好避免过度读取。
对象的无故障重读是一种 UB，如果编译器在编译时看不到它，它绝对不会受到伤害。生成的 asm 将像额外的字节是某个对象的一部分一样工作。
但即使它在编译时可见，它通常也不会受到当前编译器的影响。

PS:此答案的先前版本声称 bsf 的未对齐 deref 在为 x86 编译的 C 中也是安全的。 converting a string to upper-case with SSE2。 3年前写那部分时，我有点太傲慢了。您需要一个 int * typedef 或 __attribute__((aligned(1))) 来确保安全。
ISO C 未定义但英特尔内在函数要求编译器定义的一组内容确实包括创建未对齐的指针(至少对于 memcpy 之类的类型)，但不直接取消引用它们。 That is not true

检查指针距离 4k 页面的末尾是否足够远
这对 strlen 的第一个 vector 很有用；在此之后，您可以 __m128i* 转到下一个对齐的 vector 。如果 p = (p+16) & -16 不是 16 字节对齐，这将部分重叠，但有时进行冗余工作是设置高效循环的最紧凑方式。避免它可能意味着一次循环 1 个字节直到对齐边界，这当然更糟。
例如检查 p (LEA/XOR/TEST)，它告诉您 16 字节加载的最后一个字节与第一个字节具有相同的页面地址位。或者 ((p + 15) ^ p) & 0xFFF...F000 == 0(LEA/OR/CMP 具有更好的 ILP)检查加载的最后一个字节地址 <= 包含第一个字节的页面的最后一个字节。
或者更简单地说， p+15 <= p|0xFFF (MOV/AND/CMP)，即 p & 4095 > (4096 - 16) 检查页内偏移距页尾是否足够远。
您可以使用 32 位操作数大小来保存此检查或任何其他检查的代码大小(REX 前缀)，因为高位无关紧要。一些编译器不会注意到这种优化，因此您可以转换为 p & (pgsize-1) < (pgsize - vecwidth) 而不是 unsigned int ，尽管要消除有关不是 64 位干净的代码的警告，您可能需要转换为 uintptr_t 。使用 (unsigned)(uintptr_t)p (MOV/SHL/CMP) 可以进一步节省代码大小，因为 ((unsigned int)p << 20) > ((4096 - vectorlen) << 20) 是 3 个字节，而 shl reg, 20 是 5，或者任何其他寄存器的 6。 (使用 EAX 也将允许 and eax, imm32 的 no-modrm 短格式。)
如果在 GNU C 中执行此操作，您可能希望 cmp eax, 0xfff 使其安全地进行未对齐的访问。