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个字节(当input & 0xF == 1
时,会出现7字节的情况)。但是,返回调用具有检查,排除了发生在缓冲区末尾之外的任何虚假匹配。
实际上,在x86和x86-64上使用这样的函数是否安全?
这种类型的过度读取在高性能代码中很常见。为了避免这种过度读取,特殊的尾部代码也很常见。有时候你会看到后者替换前者以消除像valgrind这样的工具的警告。有时候你会看到一个提议去进行这样的替换,但是基于这个习惯是安全的和该工具存在错误(或者太保守),这个提议被拒绝3。对于语言专家的注释:
在标准中,读取超出其分配大小的指针是绝对不允许的。我欣赏语言律师的回答,有时甚至会自己写,当有人挖掘出章节和课文显示上面的代码是未定义行为并且因此在最严格的意义上不安全时(我将复制详细信息在这里),我甚至会感到高兴。但归根结底,这不是我追求的。作为实际问题,许多涉及指针转换、通过这些指针访问结构等常见习惯用法在技术上是未定义的,但在高质量和高性能代码中广泛使用。通常没有替代方案,或者替代方案运行速度只有一半或更低。
如果您愿意,请考虑修改此问题的版本,即:
在将上述代码编译为x86 / x86-64汇编代码之后,并且用户已验证它以预期的方式进行编译(即,编译器没有使用可证明的部分越界访问来执行某些非常聪明的操作),执行编译后的程序是否安全?
在这方面,这个问题既是一个C问题,也是一个x86汇编问题。我看到使用这个技巧的大部分代码都是用C编写的,而C仍然是高性能库的主导语言,轻松超越低级别的东西,如汇编语言,以及高级别的东西,如<所有其他东西>。至少在FORTRAN仍然打球的核心数字领域之外。因此,我对问题的视图感兴趣,这就是为什么我没有将其制定为纯x86汇编问题的原因。
话虽如此,尽管我对显示这是UD的标准链接只是适度感兴趣,但我非常感兴趣任何实际实现的细节,可以使用此特定UD生成意外代码。现在我认为这不可能发生,除非进行了一些深入的交叉过程分析,但gcc溢出的东西也让很多人感到惊讶...
1 即使在表面看来无害的情况下,例如写回相同的值,它也可能破坏并发代码。
2 注意,为了使这种重叠工作,需要该函数和match()
函数以特定的幂等方式运行-特别是返回值支持重叠检查。因此,“查找第一个匹配模式的字节”可以工作,因为所有match()
调用仍然按顺序进行。然而,“计算匹配模式的字节数”方法将不起作用,因为某些字节可能被多次计数。顺便说一下:一些函数(例如“返回最小字节”调用)即使没有按顺序限制也能工作,但需要检查所有字节。
3 需要注意的是,对于valgrind的Memcheck 有一个标志--partial-loads-ok
,用于控制此类读取是否会被报告为错误。默认值为yes,通常这种加载不会被视为立即错误,但会尝试跟踪所加载的字节的后续使用情况,其中一些是有效的,一些则无效,在使用超出范围的字节时会标记出错。在像上面的示例中,match()
中访问整个单词的情况下,这样的分析将得出字节已被访问的结论,即使结果最终被丢弃。Valgrind 通常无法确定从部分加载的无效字节是否实际使用(并且通常检测非常困难)。
shortMethod()
呢? - Barmarasm()
。 :) - Barmar