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

Question

如果允许在输入缓冲区末尾读取少量数据,则可以(并且)简化在高性能算法中找到的许多方法.这里,"少量"通常意味着W - 1超过结束的字节,其中W是算法的字节大小(例如,对于处理64位块中的输入的算法,最多7个字节).

很明显,写入输入缓冲区的末尾通常是不安全的,因为您可能会破坏缓冲区¹之外的数据.同样清楚的是,在缓冲区的末尾读取到另一页面可能会触发分段错误/访问冲突,因为下一页可能不可读.

但是,在读取对齐值的特殊情况下,页面错误似乎是不可能的,至少在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这样的工具.有时你会看到一个建议做这样的替换,这个被拒绝的理由是成语是安全的并且工具是错误的(或者只是过于保守)³.

语言律师的说明:

标准中绝对不允许从超出其分配大小的指针读取.我很欣赏语言律师的答案,甚至偶尔也会自己写一下,当有人挖出章节和节目时,我会很高兴,这些章节和节目表明上面的代码是不明确的行为,因此在严格意义上不安全(我会复制)这里的细节).但最终,这不是我追求的.实际上,许多涉及指针转换的常见习语,通过这些指针进行结构访问等等在技术上尚未定义,但在高质量和高性能代码中广泛使用.通常没有替代方案,或者替代方案以半速或更低的速度运行.

如果您愿意,请考虑此问题的修改版本,即:

将上面的代码编译成x86/x86-64程序集后,用户已经验证它是以预期的方式编译的(即,编译器没有使用可证明的部分越界访问来真正做某事聪明,正在执行编译的程序安全吗？

在这方面,这个问题既是C问题,也是x86汇编问题.使用这个技巧的大多数代码都是用C语言编写的,而C仍然是高性能库的主要语言,很容易超越像asm这样的低级内容,以及像<everything else>这样的更高级别的东西.至少在FORTRAN仍在打球的硬核数字利基之外.所以我对问题的C编译器和以下视图感兴趣,这就是为什么我没有将它表示为纯x86汇编问题.

所有这一切,虽然我对标准的链接只是中等感兴趣,显示这是UD,但我对可以使用此特定UD产生意外代码的实际实现的任何细节非常感兴趣.现在我不认为如果没有深入的深度跨程序分析就会发生这种情况,但是gcc溢出的东西也让很多人感到惊讶......

---

¹即使在看似无害的情况下,例如,在写回相同值的情况下,它也会破坏并发代码.

²注意这种重叠工作要求此函数和match()函数以特定的幂等方式运行 - 特别是返回值支持重叠检查.因此,"查找第一个字节匹配模式"有效,因为所有match()调用仍然是有序的.但是,"计数字节匹配模式"方法不起作用,因为某些字节可以重复计算.顺便说一句:一些函数,如"返回最小字节"调用,即使没有有序限制也可以工作,但需要检查所有字节.

³值得注意的是,对于valgrind的Memcheck,有一个标志,--partial-loads-ok它控制这些读取是否实际上被报告为错误.默认值为yes,表示通常这样的加载不会被视为立即错误,但是会努力跟踪后续使用的加载字节,其中一些是有效的,而另一些则不是,并且标记了错误如果外的范围中的字节中使用.在上述例子中,访问整个单词的情况下match(),这样的分析将得出结论,即使结果最终被丢弃,也会访问字节.Valgrind 通常无法确定是否实际使用了来自部分加载的无效字节(并且通常检测可能非常困难).

Answer 1

是的,它在x86 asm中是安全的,现有的libc strlen(3)实现利用了这一点.

据我所知,在为x86编译的C中它也是安全的.读取对象外部当然是C语言中的未定义行为,但它是针对C-targeting-x86定义的.我认为积极的编译器在优化时不会认为 UB不是那种UB ,但在这一点上编译器 - 编写者的确认会很好,特别是对于在编译时可以很容易地证明访问出来的情况过去一个对象的结束.(参见@RossRidge评论中的讨论:这个答案的先前版本断言它绝对安全,但LLVM博客文章并没有真正读到这种方式).

您获得的数据是不可预测的垃圾,但不会有任何其他潜在的副作用.只要您的程序不受垃圾字节的影响,它就没问题了.(例如,使用bithack来查找a __attribute__((may_alias))中的一个字节是否为零,然后使用字节循环来查找第一个零字节,而不管它之外的垃圾是什么.)

类似地,使用强制转换创建未对齐的指针是C标准中的UB(即使您不取消引用它们).在针对x86时,它在所有已知的C编译器中都有明确定义.英特尔的SSE内在函数甚至需要它; 例如,unsigned long获取一个指向未对齐的16字节的指针__m128i.

(对于AVX512,他们最终改变了这种不方便的设计选择,((p + 15) ^ p) & 0xFFF...F000 == 0以适应新的内在函数p+15 <= p|0xFFF).

甚至在为x86编译的C中解除引用未对齐uint64_t或volatile T*安全(并具有良好定义的行为).但是,strlen直接解除引用(而不是使用加载/存储内在函数)将使用0,这会对未对齐的指针产生错误.

由于性能原因,通常这样的循环避免触及他们不需要触摸的任何额外缓存行,而不仅仅是页面.

在同一页面中,存储器映射的I/O寄存器与用于宽负载循环的缓冲区,或者特别是相同的64B高速缓存行,即使你从一个调用这样的函数,也是极不可能的.设备驱动程序(或用户空间程序,如已映射某些MMIO空间的X服务器).

如果您正在处理一个60字节的缓冲区并且需要避免从4字节MMIO寄存器中读取数据,那么您就会知道它.对于普通代码,这种情况不会发生.

pminub是循环的规范示例,它处理隐式长度缓冲区,因此无法在不读取缓冲区末尾的情况下进行向量化.如果您需要避免读取超过终止pcmpeqb字节,则一次只能读取一个字节.

例如,glibc的实现使用序言来处理直到第一个64B对齐边界的数据.然后在主循环(gitweb链接到asm源)中,它使用四个SSE2对齐的加载来加载整个64B高速缓存行.它将它们合并为一个向量pmovmskb(无符号字节的最小值),因此只有当四个向量中的任何一个为零时,最终向量才会有一个零元素.在发现字符串的结尾位于该缓存行中的某个位置后,它会分别重新检查四个向量中的每一个以查看位置.(使用典型bsf的全零向量,和int */ __attribute__((aligned(1)))来找到向量中的位置.)glibc曾经有一些不同的strlen策略可供选择,但是当前的一个在所有x86-64 CPU上都很好.

一次加载64B当然只能安全地使用64B对齐的指针,因为自然对齐的访问不能跨越缓存行或页面行边界.

如果您事先知道缓冲区的长度,则可以使用在缓冲区的最后一个字节处结束的未对齐加载来处理超出最后一个对齐向量的字节,从而避免读取结束.(同样,这只适用于幂等算法,例如memcpy,它们不关心它们是否将存储重叠到目的地.原位修改算法通常不能这样做,除了将字符串转换为高位 -使用SSE2的情况,可以重新处理已经被升级的数据.除了存储转发停止,如果你做的是与最后一个对齐的商店重叠的未对齐加载.)

Answer 2

如果允许考虑非CPU设备,则可能不安全操作的一个示例是访问PCI映射的存储器页面的越界区域.无法保证目标设备使用与主内存子系统相同的页面大小或对齐方式.例如,[cpu page base]+0x800如果设备处于2KiB页面模式,则尝试访问地址可能会触发设备页面错误.这通常会导致系统错误检查.