Skip to contentSkip to conversation

C standard compliance?

DISCUSSION David Kastrup 4 participants 6 messages Jun 15, 2016

lore
Share & tools
lore

David Kastrup

author
#0 lore raw

Hi, I am wondering if I may compare pointers with < that have been created using different calls of malloc.

The C standard does not allow this (inequalities are only allowed for pointers into the same structure) to allow for some cheapskate sort of comparison in segmented architectures.

Now of course being able to _sort_ pointers also allows to _collate_ them. It totally does not matter just _what_ their ordering relation is as long as it yields to a sorting function (namely obeys some basic relations).

The question is whether this kind of undefined behavior (which almost never is implemented in unexpected ways) is frowned upon in the Git codebase or not.

Signature · 1 line
David Kastrup
#1 lore raw
Quoted 6 lines · David Kastrup

Hi, I am wondering if I may compare pointers with < that have been created using different calls of malloc.

The C standard does not allow this (inequalities are only allowed for pointers into the same structure) to allow for some cheapskate sort of comparison in segmented architectures.

Hmm... if you were to implement a set of pointers in such a way that you can cheaply tell if an unknown pointer belongs to that set, you would use a hashtable, keyed with something that is derived from the value of the pointer casted to uintptr_t, I would think. Is such a use of ((uintptr_t)ptr) unallowed? If it is allowed, comparing two unrelated pointers after casting them to uintptr_t would equally be valid, I would have to think.

author
#2 lore raw
Quoted 5 lines · Junio C Hamano
Quoted 3 lines · David Kastrup

Hi, I am wondering if I may compare pointers with < that have been created using different calls of malloc.

Quoted 8 lines
Quoted 3 lines

The C standard does not allow this (inequalities are only allowed for pointers into the same structure) to allow for some cheapskate sort of comparison in segmented architectures.

Hmm... if you were to implement a set of pointers in such a way that you can cheaply tell if an unknown pointer belongs to that set, you would use a hashtable, keyed with something that is derived from the value of the pointer casted to uintptr_t, I would think.

The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999 (C99). So it would seem that I'd be covering fewer cases rather than more in that manner.

I should think that architectures providing uintptr_t/intptr_t would have very little incentive _not_ to offer pointer inequalities equivalent to either the uintptr_t or intptr_t type conversion.

Signature · 1 line
David Kastrup
#3 lore raw
Quoted 9 lines · David Kastrup
Quoted 4 lines · Junio C Hamano

Hmm... if you were to implement a set of pointers in such a way that you can cheaply tell if an unknown pointer belongs to that set, you would use a hashtable, keyed with something that is derived from the value of the pointer casted to uintptr_t, I would think.

The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999 (C99). So it would seem that I'd be covering fewer cases rather than more in that manner.

I think we already use uintptr_t in the codebase, and if it's not present, we typedef it to unsigned long. So I think it should be fine (and well-defined) if instead of doing

void *p, *q;
...
if (p < q)

    ...

you do:

void *p, *q;
...
if ((uintptr_t)p < (uintptr_t)q)

    ...

Then on those systems where the compiler has some bizarre undefined behavior checking, the code will work. On systems that don't have uintptr_t, the compiler is probably not smart enough to perform such a check anyway.

Signature · 3 lines
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187
author
#4 lore raw
Quoted 25 lines · brian m. carlson
Quoted 9 lines · David Kastrup
Quoted 4 lines · Junio C Hamano

Hmm... if you were to implement a set of pointers in such a way that you can cheaply tell if an unknown pointer belongs to that set, you would use a hashtable, keyed with something that is derived from the value of the pointer casted to uintptr_t, I would think.

The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999 (C99). So it would seem that I'd be covering fewer cases rather than more in that manner.

I think we already use uintptr_t in the codebase, and if it's not present, we typedef it to unsigned long. So I think it should be fine (and well-defined) if instead of doing

void *p, *q;
...
if (p < q)

    ...

you do:

void *p, *q;
...
if ((uintptr_t)p < (uintptr_t)q)

Quoted 6 lines
    ...

Then on those systems where the compiler has some bizarre undefined behavior checking, the code will work. On systems that don't have uintptr_t, the compiler is probably not smart enough to perform such a check anyway.

The use case is actually sorting a list such that entries pointing to the same malloced "origin" data structure are in adjacent list positions. At list intptr_t seems used plentifully in Git.

Signature · 1 line
David Kastrup
#5 lore raw
In reply to David Kastrup

From: "David Kastrup" <[email protected]>

Quoted 18 lines
Quoted 11 lines · Junio C Hamano
Quoted 8 lines · David Kastrup

Hi, I am wondering if I may compare pointers with < that have been created using different calls of malloc.

The C standard does not allow this (inequalities are only allowed for
pointers into the same structure) to allow for some cheapskate sort of
comparison in segmented architectures.

Quoted 4 lines

Hmm... if you were to implement a set of pointers in such a way that you can cheaply tell if an unknown pointer belongs to that set, you would use a hashtable, keyed with something that is derived from the value of the pointer casted to uintptr_t, I would think.

Quoted 8 lines

The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999 (C99). So it would seem that I'd be covering fewer cases rather than more in that manner.

I should think that architectures providing uintptr_t/intptr_t would have very little incentive _not_ to offer pointer inequalities equivalent to either the uintptr_t or intptr_t type conversion.

Undefined behaviours become hidden bugs of the future...
http://article.gmane.org/gmane.comp.version-control.git/230583

"blog on the problems of unexpected optimization bugs,
such as dereferencing a null pointer. "Finding Undefined Behavior Bugs by Finding Dead Code" http://blog.regehr.org/archives/970 which links to the draft of an interesting paper
http://pdos.csail.mit.edu/~xi/papers/stack-sosp13.pdf"

The code has now been released http://css.csail.mit.edu/stack/
https://github.com/xiw/stack/, and a few potential errors in Git were caught by that tool by Stefan Beller.

The key point of the paper was never to try to use an 'obvious', but undefined, behaviour.

--
Philip