* C standard compliance?
@ 2014-01-29 20:33 David Kastrup
2014-01-29 20:42 ` Junio C Hamano
0 siblings, 1 reply; 6+ messages in thread
From: David Kastrup @ 2014-01-29 20:33 UTC (permalink / raw)
To: git
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.
--
David Kastrup
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: C standard compliance?
2014-01-29 20:33 C standard compliance? David Kastrup
@ 2014-01-29 20:42 ` Junio C Hamano
2014-01-29 20:52 ` David Kastrup
0 siblings, 1 reply; 6+ messages in thread
From: Junio C Hamano @ 2014-01-29 20:42 UTC (permalink / raw)
To: David Kastrup; +Cc: git
David Kastrup <dak@gnu•org> writes:
> 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.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: C standard compliance?
2014-01-29 20:42 ` Junio C Hamano
@ 2014-01-29 20:52 ` David Kastrup
2014-01-29 23:00 ` Philip Oakley
2014-01-29 23:33 ` brian m. carlson
0 siblings, 2 replies; 6+ messages in thread
From: David Kastrup @ 2014-01-29 20:52 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
Junio C Hamano <gitster@pobox•com> writes:
> David Kastrup <dak@gnu•org> writes:
>
>> 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.
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.
--
David Kastrup
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: C standard compliance?
2014-01-29 20:52 ` David Kastrup
@ 2014-01-29 23:00 ` Philip Oakley
2014-01-29 23:33 ` brian m. carlson
1 sibling, 0 replies; 6+ messages in thread
From: Philip Oakley @ 2014-01-29 23:00 UTC (permalink / raw)
To: David Kastrup; +Cc: Git List, Junio C Hamano
From: "David Kastrup" <dak@gnu•org>
> Junio C Hamano <gitster@pobox•com> writes:
>
>> David Kastrup <dak@gnu•org> writes:
>>
>>> 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.
>
> 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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: C standard compliance?
2014-01-29 20:52 ` David Kastrup
2014-01-29 23:00 ` Philip Oakley
@ 2014-01-29 23:33 ` brian m. carlson
2014-01-30 0:02 ` David Kastrup
1 sibling, 1 reply; 6+ messages in thread
From: brian m. carlson @ 2014-01-29 23:33 UTC (permalink / raw)
To: git
[-- Attachment #1: Type: text/plain, Size: 1314 bytes --]
On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote:
> Junio C Hamano <gitster@pobox•com> writes:
> > 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.
--
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
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: C standard compliance?
2014-01-29 23:33 ` brian m. carlson
@ 2014-01-30 0:02 ` David Kastrup
0 siblings, 0 replies; 6+ messages in thread
From: David Kastrup @ 2014-01-30 0:02 UTC (permalink / raw)
To: git
"brian m. carlson" <sandals@crustytoothpaste•net> writes:
> On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote:
>> Junio C Hamano <gitster@pobox•com> writes:
>> > 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.
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.
--
David Kastrup
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2014-01-30 0:02 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-01-29 20:33 C standard compliance? David Kastrup
2014-01-29 20:42 ` Junio C Hamano
2014-01-29 20:52 ` David Kastrup
2014-01-29 23:00 ` Philip Oakley
2014-01-29 23:33 ` brian m. carlson
2014-01-30 0:02 ` David Kastrup
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox