代码之家 › 专栏 › 技术社区 › Pascal Cuoq

如何在没有中间副本的情况下在标准C中实现memmove?

unspecified-behavior undefined-behavior c99 c

Pascal Cuoq · 技术社区 · 14 年前

从我的系统上的手册页:

void*memmove(void*dst,const void*src,size\u t len);

描述
函数的作用是:将len字节从string src复制到string dst。
两个字符串可能重叠 ;复制总是在非破坏性的
态度。

根据C99标准:

6.5.8.5当比较两个指针时,结果取决于地址中的相对位置指向对象的空间。如果指向对象的两个指针或不完整两种类型都指向同一对象, 或者都是最后一点相同数组对象的元素, 它们是相等的。如果对象指向的是相同的成员聚合对象,指向稍后声明的结构成员比较大于指针到先前在结构和指向数组的指针下标值较大的元素比较大于指针到同一数组的元素下标值。指向所有指针同一联合对象的成员比较相等。如果表达式 P 指向数组的元素对象和表达式q指向同一数组的最后一个元素对象,指针表达式 Q+1 比较大于 磷 . 总共其他情况下,行为是 未定义 .

重点是我的。

论点 dst 和 src 无法转换为指向 char 为了减轻严格的混叠问题,但是是否可以比较可能指向不同块内的两个指针,以便在它们指向同一块内时按正确的顺序进行复制?

显而易见的解决办法是 if (src < dst) ,但如果 SRC 和 DST 指向不同的块。”“未定义”表示您甚至不应假定条件返回0或1(在标准词汇表中,这称为“未指定”)。

另一种选择是 if ((uintptr_t)src < (uintptr_t)dst) ,这至少是未指明的,但我不确定标准是否保证 src < dst 是定义的,它等价于 (uintptr_t)src < (uintptr_t)dst) . 指针比较是根据指针算法定义的。例如,当我阅读第6.5.6节关于加法的内容时,在我看来指针算术的方向可能与 uintptr_t 也就是说,当 p 属于类型 char* :

((uintptr_t)p)+1==((uintptr_t)(p-1)

这只是一个例子。一般来说,当将指针转换为整数时,几乎没有什么保证。

这是一个纯粹的学术问题,因为 memmove 与编译器一起提供。在实践中,编译器作者可以简单地将未定义的指针比较提升为未指定的行为,或者使用相关的pragma强制编译器编译它们的 默默斯 正确地。例如, this implementation 包含以下代码段:

if ((uintptr_t)dst < (uintptr_t)src) {
            /*
             * As author/maintainer of libc, take advantage of the
             * fact that we know memcpy copies forwards.
             */
            return memcpy(dst, src, len);
    }

我仍然想用这个例子来证明标准在未定义的行为下走得太远,如果这是真的 默默斯 不能在标准C中有效地实现。例如,在回答时没有人打勾。 this SO question .

5 回复 | 直到 8 年前

Steve Jessop 13 年前

我认为你是对的,不可能实现 memmove 在标准C中有效。

我认为,测试区域是否重叠的唯一真正可移植的方法是这样的:

[编辑:以后再看,我想应该是 dst+len-1 在第二行的末尾。但是我不必费心去测试它,所以我现在就离开,可能我第一次知道我在说什么。]

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len) {
      // they overlap, so now we can use comparison,
      // and copy forwards or backwards as appropriate.
      ...
      return dst;
    }
}
// No overlap, doesn't matter which direction we copy
return memcpy(dst, src, len);

你也不能实现 memcpy 或 默默斯 全部的那个在可移植代码中效率很高,因为平台特定的实现很可能会让您的工作受到影响。但是便携式 曼皮西 至少看起来是合理的。

C++引入指针专业化 std::less ,它被定义为适用于同一类型的任何两个指针。理论上可能比 < 但很明显,在非分段的架构中,它不是。

C没有这样的东西,所以从某种意义上说,C++标准同意C没有足够定义的行为。但是,C++需要它 std::map 等等。你更可能想实施 STD::地图 (或类似的事情)不知道实现,而不是你想要实现的 默默斯 (或类似的事情)不知道实施。

Lou Franco 14 年前

对于两个有效且重叠的内存区域,我相信您需要处于6.5.8.5中定义的情况之一。也就是说,数组、联合、结构等的两个区域。

其他情况未定义的原因是两个不同的对象甚至可能不在同一类型的内存中,具有相同类型的指针。在PC体系结构中,地址通常只是虚拟内存中的32位地址,但是C支持各种奇怪的体系结构,在这些体系结构中,内存不是这样的。

C不定义事物的原因是在不需要定义情况时给编译器编写者让路。阅读6.5.8.5的方法是一个段落,它详细描述了C想要支持的体系结构,如果指针比较没有意义,除非它在同一个对象中。

另外,编译器提供memmove和memcpy的原因是,它们有时使用专门的指令编写在目标CPU的调优程序集中。它们并不意味着能够以相同的效率在C中实现。

bta 14 年前

首先,C标准因在细节方面存在问题而臭名昭著。部分问题是因为C用于多个平台,并且标准尝试足够抽象以涵盖所有当前和未来的平台(这可能使用一些复杂的内存布局,这是我们从未见过的)。为了让编译器编写者为目标平台“做正确的事情”,有许多未定义的或特定于实现的行为。包含每个平台的详细信息是不切实际的(而且经常过时);相反,C标准将其留给编译器编写者来记录在这些情况下发生的事情。”“未指定”行为只意味着C标准没有指定发生了什么,不一定是无法预测结果。如果您阅读目标平台和编译器的文档,结果通常仍然是可预测的。

由于确定两个指针是否指向同一个块、内存段或地址空间取决于该平台的内存布局方式,所以规范没有定义进行该确定的方法。它假定编译器知道如何做出这个决定。您引用的规范部分说,指针比较的结果取决于指针的“地址空间中的相对位置”。注意,“地址空间”在这里是单数。本节仅指位于同一地址空间中的指针;即直接可比较的指针。如果指针位于不同的地址空间中,那么结果将由C标准定义,而不是由目标平台的要求定义。

在情况下 memmove ,实现者通常首先确定地址是否可直接比较。如果没有,那么函数的其余部分是特定于平台的。大多数情况下,处于不同的内存空间足以确保区域不重叠,并且该函数将变为 memcpy . 如果地址是直接可比较的,那么它只是一个简单的字节复制过程,从第一个字节开始,向前或从最后一个字节开始,向后(无论哪一个都可以安全地复制数据,而不会造成任何损坏)。

总之,C标准有很多故意未指定的地方,因为它不能在任何目标平台上编写一个简单的规则。然而,标准作家本可以做得更好的解释 为什么 有些东西没有被定义和使用更具描述性的术语,比如“依赖于体系结构”。

R.. GitHub STOP HELPING ICE 14 年前

这是另一个想法,但我不知道它是否正确。避免 O(len) 把史蒂夫的答案圈起来,你可以把它放进 #else An子句 #ifdef UINTPTR_MAX 和演员一起- uintptr_t 实施。但前提是 unsigned char * 到 尤因普特里特 只要偏移量对指针有效,就可以通过添加整数偏移量进行通勤,这使得指针比较定义良好。

我不确定这个交换性是不是由标准定义的,但是它是有意义的,因为它是有效的,即使指针的低位是一个实际的数字地址,高位是某种黑盒。

JeremyP 14 年前

我仍然想用这个例子来证明标准在未定义的行为下走得太远,如果在标准C中MemMove不能有效地实现是真的。

但这不是证据。绝对无法保证您可以比较任意机器体系结构上的两个任意指针。这种指针比较的行为不能由C标准甚至编译器来规定。我可以想象一台具有分段结构的机器,它可能会根据段在RAM中的组织方式产生不同的结果,甚至可能在比较不同段中的指针时选择抛出异常。这就是行为“未定义”的原因。在完全相同的机器上运行完全相同的程序可能会在运行到运行之间产生不同的结果。

memmove()的经常给出的“解决方案”使用两个指针的关系来选择是从开始复制到结束还是从结束复制到开始只有在所有内存块都从相同的地址空间分配时才有效。幸运的是,这种情况通常是这样的,尽管它不是在16位x86代码的时代。