threads / discuss / 35759

C standard compliance?

Subject: C standard compliance?

## tl;dr

6 messages between Jan 29, 2014 and Jan 30, 2014.

replies: 5people: 4as markdown or json

David Kastrup· Jan 29, 2014, 20:33 UTC · lore

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
Junio C Hamano· Jan 29, 2014, 20:42 UTC · re: David Kastrup · lore

Re: C standard compliance?

David Kastrup <dak@gnu.org> writes:
Show 6 quoted lines
> 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.

David Kastrup· Jan 29, 2014, 20:52 UTC · re: Junio C Hamano · lore

Re: C standard compliance?

Junio C Hamano <gitster@pobox.com> writes:
Show 13 quoted lines
> 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
Philip Oakley· Jan 29, 2014, 22:21 UTC · re: David Kastrup · lore

Re: C standard compliance?

From: "David Kastrup" <dak@gnu.org>
Show 26 quoted lines
> 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

brian m. carlson· Jan 29, 2014, 23:33 UTC · re: David Kastrup · lore

Re: C standard compliance?

On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote:
Show 9 quoted lines
> 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
David Kastrup· Jan 30, 2014, 00:02 UTC · re: brian m. carlson · lore

Re: C standard compliance?

"brian m. carlson" <sandals@crustytoothpaste.net> writes:
Show 31 quoted lines
> 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

← back to recent threads