是什么让glibc malloc可以比较来自不同“对象”的指针?
比较指针与关系运算符(例如<
, <=
, >=
或>
)仅在指针指向同一聚合对象(结构,数组或联合)时由C标准定义。 这在实践中意味着形状的比较
if (start_object <= my_pointer && my_pointer < end_object+1) {
可以变成
if (1) {
通过优化编译器。 尽管如此,在K&R的第8.7节“示例 – 存储分配器”中,作者进行了与上述类似的比较。 他们原谅这个说法
然而,仍有一个假设是,可以有意义地比较
sbrk
返回的不同块的指针。 标准不保证这一点,它只允许在数组中进行指针比较。 因此,这个版本的malloc
只能在一般指针比较有意义的机器之间移植。
而且,看来glibc
中使用的malloc
的实现做了同样的事情!
更糟糕的是 – 我偶然发现这一点的原因是 – 对于学校作业,我应该实现一个基本的类似function,并且作业的指示要求我们使用K&R代码,但我们必须更换通过调用mmap
调用sbrk
!
虽然比较来自不同sbrk
调用的指针可能是未定义的,但它也只是略微可疑,因为你有某种心理直觉,返回的指针应该来自同一个内存区域。 根据我的理解,由不同的mmap
调用返回的指针甚至不能保证彼此远程相似,并且在mmap调用之间合并/合并内存块应该是非常非法的(并且看起来glibc
避免了这种情况,只采用合并由sbrk
或mmap
页面内部返回的内存,而不是它们之间的内存),但是赋值需要这样。
问题:有人可以发光
- 是否可以优化将来自不同调用的指针与
sbrk
进行比较 - 如果是这样,
glibc
做什么让他们逃脱它。
语言律师答案是(我相信)可以在C99标准的§6.5.8.5中找到(或者更确切地说来自ISO / IEC 9899:TC3委员会草案 – 2007年7月7日WG14 / N1256,它几乎相同,但我不知道t有原始的手)关于关系运算符(即<
, <=
, >
, >=
)具有以下内容:
比较两个指针时,结果取决于指向的对象的地址空间中的相对位置。 如果指向对象或不完整类型的两个指针都指向同一个对象,或者两个指针都指向同一个数组对象的最后一个元素,则它们相等。 如果指向的对象是同一聚合对象的成员,则指向稍后声明的结构成员的指针比指向结构中先前声明的成员的指针大,指向具有较大下标值的数组元素的指针比指向同一数组的元素的指针大。具有较低的下标值。 指向同一union对象成员的所有指针都比较相等。 如果表达式
P
指向数组对象的元素并且表达式Q
指向同一数组对象的最后一个元素,则指针表达式Q+1
比P
。 在所有其他情况下,行为未定义。
(C11文本相同或几乎相同)
这开始似乎没有用,或者至少表明每个实现都利用未定义的行为。 但是,我认为,您可以合理化行为或使用解决方法。
指定的C指针要么是NULL
,要么是通过使用&
,或通过指针算法或某些函数的结果获取对象的地址而得到的。 在有关的情况下,它们是由sbrk
或mmap
系统调用的结果派生的。 这些系统真正回归的是什么? 在寄存器级别,它们返回一个大小为uintptr_t
(或intptr_t
)的整数。 它实际上是系统调用接口,它将它们转换为指针。 我们知道指针之间的转换和uintptr_t
(或intptr_t
)是双向类型的定义,我们知道我们可以将指针uintptr_t
为uintptr_t
(例如)并比较它们,这将对指针强加一个井顺序关系 。 维基百科链接提供了更多信息,但这实质上将确保每个比较都得到很好的定义以及其他有用的属性,例如a和
b
a
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位内存) - 尽管注意到过去已经开发了类似的环绕。
C标准规定指针比较在许多情况下给出未定义的结果。 但是,在这里,您要使用系统调用返回的整数构建自己的指针。 因此,您可以比较整数,或者通过将它们转换回整数来比较指针(利用强制转换的双射性质)。 如果你只是比较指针,你依赖于C编译器的指针比较实现是理智的,几乎可以肯定,但不能保证。
我提到的可能性是如此模糊,以至于可以打折吗? 不,让我们找一个它们可能很重要的平台示例:8086。可以想象一个8086编译模型,其中每个指针都是一个“远”指针(即包含一个段寄存器)。 指针比较可以在段寄存器上执行<
或>
,并且只有它们相等时才对偏移执行<
或>
。 只要C99§6.5.8.5中的所有结构都属于同一段,这就完全合法。 但它不会像人们预期的那样在段之间起作用,因为1000:1234
(在内存地址中等于1010:1134
)将显得小于1010:0123
。 这里的mmap
可能会在不同的段中返回结果。 类似地,人们可以想到另一个存储器模型,其中段寄存器实际上是一个选择器,并且指针比较使用处理器比较指令来比较存储器地址,如果使用无效选择器或段外的偏移则中止该存储器地址。
你问两个具体问题:
是否可以优化将来自不同调用的指针与
sbrk
进行比较如果是这样,glibc会做什么让他们逃脱它。
在上面给出的start_object
等实际上是void *
的公式中, 可以优化计算(即可能做你想要的),但不能保证这样做,因为行为是未定义的。 如果内核使用与强制转换所暗示的相同的井顺序,则转换将保证它这样做。
在回答第二个问题时, glibc
依赖于C编译器的行为,这在技术上并不是必需的,但非常可能(按照上述内容)。
另请注意(至少在我前面的K&R中)您引用的行在代码中不存在。 警告是关于header *
指针与<
的比较(因为我可以看到void *
指针与<
总是UB的比较),这可能来自单独的sbrk()
调用。
答案很简单。 C库实现是根据官方规范的一些知识(或可能期望)C编译器如何处理具有未定义行为的某些代码而编写的。
我可以给出很多例子; 但是这些指针实际上是指进程’地址空间中的一个地址,并且可以自由地进行比较,这是由C库实现(至少由Glibc)以及许多“真实世界”程序所依赖的。 虽然严格符合程序的标准不能保证,但绝大多数真实世界的架构/编译器都是如此。 另请注意脚注67,关于将指针转换为整数和后退:
用于将指针转换为整数或整数到指针的映射函数旨在与执行环境的寻址结构一致。
虽然这并不严格授予比较任意指针的许可,但它有助于理解规则应该如何工作:作为一组特定行为,确保在所有平台上保持一致,而不是作为对允许的限制当指针的表示完全已知并被理解时。
你已经说过:
if (start_object <= my_pointer && my_pointer < end_object+1) {
可以变成:
if (1) {
假设(你没有说明) my_pointer
是以某种方式从start_object
的值或它划分的对象的地址派生的 - 那么这是严格正确的,但它不是编译器在实践中所做的优化,除非在静态/自动存储持续时间对象的情况下(即编译器知道的对象未动态分配)。
考虑到对sbrk
调用被定义为根据某个brk
地址,通过给定的incr
参数来增加或减少在某些区域(堆)中分配的字节数。 这实际上只是brk
一个包装器,它允许你调整堆的当前顶部。 当你调用brk(addr)
,你告诉内核从addr
的底部一直为你的进程分配空间(或者可能是当前先前的高位地址顶部到新的空间之间的空闲空间)地址)。 如果incr == new_top - original_top
则sbrk(incr)
将完全等效。 这样回答你的问题:
-
因为
sbrk
只是通过incr
字节数来调整堆的大小(即一些连续的内存区域),比较sbrk
的值只是在一些连续的内存区域中的点的比较。 这完全等同于比较数组中的点,因此它是根据C标准的明确定义的操作。 因此,可以优化远离sbrk
指针比较调用。 -
glibc
并没有做任何特别的事情来“逃避它” – 他们只是假设上面提到的假设是正确的(它确实如此)。 事实上,如果他们正在检查用mmap
分配的内存块的状态,它会明确地validationmmap
的内存超出了用sbrk
分配的范围。
编辑:我想让我的答案更清楚:这里的关键是没有未定义的行为! sbrk
被定义为在某个连续的内存区域中分配字节,这本身就是C标准指定的“对象”。 因此,比较“对象”中的指针是一个完全理智且定义明确的操作。 这里的假设不是glibc利用未定义的指针比较,而是假设sbrk
在某个连续区域中增长/缩小内存。
C标准的作者认识到存在一些分段存储器硬件平台,其中尝试在不同段中的对象之间执行关系比较可能表现奇怪。 而不是说这样的平台无法有效地适应高效的C实现,标准的作者允许这样的实现做任何他们认为合适的事情,如果尝试将指针与可能在不同段中的对象进行比较。
对于标准的作者来说,不相交的对象之间的比较应该只在这样的分段记忆系统上表现出奇怪的行为而不能有效地产生一致的行为,这被认为暗示这样的系统不如平台之间的关系比较任意指针将产生一致的排名,标准的作者不遗余力地避免这种影响。 相反,他们认为,由于没有理由针对普通平台实现针对这种比较做任何奇怪的事情,这样的实现将合理地处理它们是否标准强制要求它们。
不幸的是,一些人对制作符合标准的编译器比制作符合标准的编译器更感兴趣的人已经决定,为了适应几十年来已经过时的硬件限制而编写的任何代码都应该被视为“破坏” ”。 他们声称他们的“优化”允许程序比其他方式更有效,但在许多情况下,“效率”增益仅在编译器省略实际必要的代码的情况下才有意义。 如果程序员解决了编译器的限制,那么结果代码可能最终效率低于编译器首先没有打扰“优化”的情况。