在x86和x64上读取同一页面内的缓冲区末尾是否安全?
如果允许在输入缓冲区末尾读取少量数据,那么在高性能算法中发现的许多方法都可以(并且被简化)。 这里,“少量”通常意味着超过结尾的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 = 0) { return input + res; } // align pointer to the next 8-byte boundary input64 = (ptrdiff_t)(input64 + 1) & ~0x7; for (; input64 0) { return input + res < input + size ? input + res : -1; } } return -1; }
内部函数int match(uint64_t bytes)
未显示,但它是查找匹配某个模式的字节,并返回最低位置(0-7)(如果找到)或否则返回-1。
首先,为了简化说明,将大小<8的情况标注为另一个函数。 然后对前8个(未对齐字节)进行单个检查。 然后为8字节2的剩余floor((size - 7) / 8)
块完成循环。 该循环可以在缓冲区末尾读取最多7个字节(当input & 0xF == 1
时发生7字节情况)。 但是,返回调用有一个检查,它排除了在缓冲区末尾之外发生的任何虚假匹配 。
实际上,在x86和x86-64上这样的function是否安全?
这些类型的重写在高性能代码中很常见。 避免这种重读的特殊尾部代码也很常见。 有时你会看到后一种类型取代前者来沉默像valgrind这样的工具。 有时候你会看到一个建议做这样的替换,这个被拒绝的理由是成语是安全的并且工具是错误的(或者过于保守) 3 。
语言律师的说明:
标准中绝对不允许从超出其分配大小的指针读取。 我很欣赏语言律师的答案,偶尔也会自己写一下,当有人挖出章节和节目时,我会很高兴,这些章节和节目表明上面的代码是不明确的行为 ,因此在最严格意义上不安全(我会复制)这里的细节)。 最终,这不是我追求的。 实际上,许多涉及指针转换的常见习语,通过这些指针进行结构访问等等在技术上尚未定义,但在高质量和高性能代码中广泛使用。 通常没有替代方案,或者替代方案以半速或更低的速度运行。
如果您愿意,请考虑此问题的修改版本,即:
将上面的代码编译成x86 / x86-64程序集后,用户已经validation它是以预期的方式编译的(即,编译器没有使用可certificate的部分越界访问来真正做某事聪明 ,正在执行编译的程序安全吗?
在这方面,这个问题既是C问题,也是x86汇编问题。 使用这个技巧的大部分代码都是用C语言编写的,C仍然是高性能库的主要语言,很容易超越像asm这样的低级内容,以及像这样的更高级别的东西。 至少在FORTRAN仍在打球的铁杆数值利基之外。 所以我对C-compiler-and-below视图的问题很感兴趣,这就是为什么我没有将它表示为纯x86汇编问题。
所有这些都说,虽然我对标准的链接只是中度感兴趣,这显示这是UD,但我对实际实现的任何细节都非常感兴趣,可以使用这个特定的UD来产生意外的代码。 现在我不认为如果没有深入的深度跨程序分析就会发生这种情况,但是gcc溢出的东西也让很多人感到惊讶……
1即使在看似无害的情况下,例如,在写回相同值的情况下,它也会破坏并发代码 。
2注意这种重叠工作要求此函数和match()
函数以特定的幂等方式运行 – 特别是返回值支持重叠检查。 因此,“查找第一个字节匹配模式”可以工作,因为所有match()
调用仍然是有序的。 但是,“计数字节匹配模式”方法不起作用,因为某些字节可以重复计算。 顺便说一下:即使没有有序限制,某些函数如“返回最小字节”调用也会起作用,但需要检查所有字节。
3值得注意的是,对于valgrind的Memcheck, 有一个标志 , – --partial-loads-ok
,它控制这些读取是否实际上被报告为错误。 默认值为yes ,表示通常不会将此类加载视为立即错误,但会努力跟踪后续使用的加载字节,其中一些是有效的,而另一些则不是,并且标记了错误如果使用超出范围的字节。 在上面例子中,在match()
访问整个单词的情况下,这样的分析将结束访问字节,即使结果最终被丢弃。 Valgrind 通常无法确定是否实际使用了来自部分加载的无效字节(并且通常检测可能非常困难)。
是的,它在x86 asm中是安全的, 现有的libc strlen(3)
实现利用了这一点。
据我所知,在为x86编译的C中它也是安全的。 读取对象外部当然是C中的未定义行为,但它对于C-targeting-x86来说是很好的定义。 我认为积极的编译器在优化时不会认为 UB不是那种UB,但是在这一点上编译器 – 编写者的确认会很好,特别是对于在编译时很容易certificate访问出来的情况过去一个对象的结束。 (请参阅@RossRidge的评论中的讨论:此答案的先前版本声称它绝对安全,但LLVM博客文章并未真正以这种方式阅读)。
您获得的数据是不可预测的垃圾,但不会有任何其他潜在的副作用。 只要你的程序不受垃圾字节的影响,它就没问题了。 (例如,使用bithack来查找uint64_t
的一个字节是否为零 ,然后使用字节循环来查找第一个零字节,而不管它之外的垃圾是什么。)
类似地,使用强制转换创建未对齐的指针是C标准中的UB(即使您不取消引用它们)。 在针对x86时,它在所有已知的C编译器中都有明确定义。 英特尔的SSE内在函数甚至需要它; 例如__m128i _mm_loadu_si128 (__m128i const* mem_addr)
获取一个指向未对齐的16字节__m128i
的指针。
(对于AVX512,他们最终将这种不方便的设计选择改为void*
用于新的内在函数,如__m512i _mm512_loadu_si512 (void const* mem_addr)
)。
甚至解除引用未对齐的uint64_t*
或int*
在为x86编译的C中是安全的(并且具有良好定义的行为)。 但是,直接解除引用__m128i*
(而不是使用加载/存储内在函数)将使用movdqa
,它会对未对齐的指针产生错误。
由于性能原因,通常这样的循环避免触及他们不需要触摸的任何额外缓存行,而不仅仅是页面。
在同一页面中,存储器映射的I / O寄存器与用于宽负载循环的缓冲区,特别是相同的64B高速缓存行极不可能,即使您从一个调用这样的函数设备驱动程序(或用户空间程序,如已映射某些MMIO空间的X服务器)。
如果您正在处理一个60字节的缓冲区并且需要避免从4字节MMIO寄存器读取数据,那么您就会知道它。 普通代码不会发生这种情况。
strlen
是循环的规范示例 ,它处理隐式长度缓冲区,因此无法在不读取缓冲区末尾的情况下进行向量化。 如果需要避免读取超过0
的终止字节,则一次只能读取一个字节。
例如,glibc的实现使用序言来处理直到第一个64B对齐边界的数据。 然后在主循环(gitweb链接到asm源)中 ,它使用四个SSE2对齐的加载来加载整个64B高速缓存行。 它使用pminub
(无符号字节的最小值)将它们合并为一个向量,因此只有当四个向量中的任何一个为零时,最终向量才会具有零元素。 在发现字符串的结尾位于该缓存行中的某个位置后,它会分别重新检查四个向量中的每一个以查看位置。 (使用典型的pcmpeqb
对全向量的向量,并使用pmovmskb
/ bsf
来找到向量中的位置。)glibc曾经有几种不同的strlen策略可供选择 ,但是当前的一个对所有x86-64都很好的CPU。
一次加载64B当然只能安全地使用64B对齐的指针,因为自然对齐的访问不能跨越缓存行或页面行边界 。
如果您事先知道缓冲区的长度,则可以使用在缓冲区的最后一个字节处结束的未对齐加载来处理超出最后一个对齐向量的字节,从而避免读取结束。 (同样,这只适用于幂等算法,例如memcpy,它们不关心它们是否将存储重叠到目的地。原位修改算法通常不能这样做,除非将字符串转换为高位 -使用SSE2的情况,可以重新处理已经被升级的数据。除了存储转发停止,如果你执行与最后一个对齐的存储重叠的未对齐负载。)
如果允许考虑非CPU设备,则可能不安全操作的一个示例是访问PCI映射的存储器页面的越界区域。 无法保证目标设备使用与主内存子系统相同的页面大小或对齐方式。 例如,如果设备处于2KiB页面模式,则尝试访问地址[cpu page base]+0x800
可能会触发设备页面错误。 这通常会导致系统错误检查。