c - 是什么使glibc malloc可以比较来自不同 "objects"的指针？

Question

仅当指针都指向同一个聚合对象(结构，数组或 union )时，才由C标准定义将指针与关系运算符(例如<，<=，>=或>)进行比较。实际上，这意味着在形状上进行比较

if (start_object <= my_pointer && my_pointer < end_object+1) {

可以变成

if (1) {

通过优化的编译器。尽管如此，在K＆R的第8.7节“示例-存储分配器”中，作者进行了与上述相似的比较。他们说这个借口

There is still one assumption, however, that pointers to different blocks returned by sbrk can be meaningfully compared. This is not guaranteed by the standard, which permits pointer comparisons only within an array. Thus this version of malloc is portable only among machines for which general pointer comparison is meaningful.

此外，看来 the implementation of malloc used in glibc 也做同样的事情!

更糟糕的是-我偶然发现它的原因是-对于学校作业，我应该实现基本的 malloc之类的功能，并且作业说明要求我们使用K＆R代码，但我们必须替换调用 sbrk来调用 mmap!

虽然比较来自不同 sbrk调用的指针可能是未定义的，但这也只是一点点可疑，因为您有某种直觉，即返回的指针应该来自相同的内存区域。据我所知，不同的 mmap调用返回的指针甚至不能保证彼此遥远相似，并且跨mmap调用合并/合并内存块应该是非常非法的(而且 glibc似乎避免了这种情况，只能通过合并来实现)由 sbrk返回的内存或在 mmap页面内部(而不是跨页面)的内存)，但是分配需要这样做。

问题:有人可以照亮吗

是否可以将来自不同调用的指针与sbrk的比较是否优化，以及

如果是这样，那么glibc会执行哪些操作，使他们摆脱它。

Answer 1

语言律师的答案(我相信)可以在C99标准的6.5.8.5节中找到(或更准确地说，来自ISO/IEC 9899:TC3委员会草案— 2007年9月7日，WG14/N1256，该文本几乎相同，但我不知道)关于关系运算符(即<，<=，>，>=)具有以下内容:

When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

(C11文本相同或几乎相同)

起初这似乎无济于事，或者至少表明每个实现都利用未定义的行为。我认为，但是，您可以使行为合理化，也可以使用变通方法。

指定的C指针要么是 NULL，要么是通过使用 &获取对象的地址派生的，或者是通过指针算术或某些函数的结果派生的。在有关情况下，它们是由 sbrk或 mmap系统调用的结果派生的。这些系统调用真正返回了什么？在寄存器级别，它们返回一个大小为 uintptr_t(或 intptr_t)的整数。实际上，正是系统调用接口(interface)将它们强制转换为指针。正如我们所知道的，指针和 uintptr_t(或 intptr_t)之间的强制转换是通过bijective类型定义的，我们知道我们可以将指针转换为 uintptr_t(例如)并进行比较，这将在指针上加上 well order relation。 Wikipedia链接提供了更多信息，但是从本质上讲，这将确保正确定义每个比较以及其他有用的属性(例如 a<b和 b<c意味着 a<c)。 (我也不能选择完全任意的顺序，因为它需要满足C99§6.5.8.5的其他要求，这几乎让我只有 intptr_t和 uintptr_t作为候选者。)

我们可以利用它来编写(可以说更好):

if ((uintptr_t)start_object <= (uintptr_t)my_pointer && (uintptr_t)my_pointer < (uintptr_t)(end_object+1)) {

这里有一个尼特。您会注意到我强制转换为 uintptr_t而不是 intptr_t。为什么这是正确的选择？实际上，为什么我没有选择一个相当奇怪的顺序，例如反转位并进行比较？这里的假设是我选择与内核相同的顺序，特别是我对 <的定义(由该顺序给出)是这样的，即任何分配的内存块的开始和结束都将始终为 start < end。在我所知道的所有现代平台上，都没有“回绕”(例如，内核不会分配从 0xffff8000开始到 0x00007ffff结束的32位内存)-尽管请注意类似的回绕 has been exploited in the past。

C标准指定在许多情况下指针比较均会给出不确定的结果。但是，这里您是根据系统调用返回的整数构建自己的指针。因此，您可以比较整数，也可以通过将指针转换回整数来比较指针(利用转换的双射性质)。如果仅比较指针，则可以依靠C编译器的指针比较实现保持理智，这几乎可以肯定是肯定的，但不能保证。

我提到的可能性是否太晦涩，无法打折？不会，让我们找到一个平台示例，它们可能很重要:8086。可以想象一个8086编译模型，其中每个指针都是一个“远”指针(即包含一个段寄存器)。指针比较可以在段寄存器上执行 <或 >，并且只有相等时才可以在偏移量上使用 <或 >。只要C99§6.5.8.5中的所有结构都在同一段中，这将是完全合法的。但它不会像人们期望的那样在段之间起作用，因为 1000:1234(等于内存地址中的 1010:1134)看起来会小于 1010:0123。此处的 mmap可能会在不同的段中返回结果。类似地，可以想到另一种内存模型，其中段寄存器实际上是选择器，并且指针比较使用处理器比较指令来比较内存地址，如果使用了无效的选择器或段外部的偏移量，则该内存地址将中止。

您问两个具体问题:

1. Whether or not comparing pointers from different calls to sbrk may be optimised away, and

2. If so, what glibc does that lets them get away with it.

在上面给出的公式中 start_object等实际上是 void *，然后可以优化计算(即可以执行您想要的操作)，但不能保证这样做，因为行为是不确定的。如果内核使用与强制转换隐含的相同的良好顺序，则强制转换将保证这样做。

在回答第二个问题时， glibc依赖于C编译器的行为，这在技术上不是必需的，但很有可能(根据以上所述)。

还请注意(至少在我前面的K＆R中)，您引用的行在代码中不存在。需要注意的是， header *指针与 <的比较(据我所知， void *指针与 <的比较始终是UB)，这可能来自于单独的 sbrk()调用。