C standard compliance?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: C standard compliance?
David Kastrup d...@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. -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: C standard compliance?
Junio C Hamano gits...@pobox.com writes: David Kastrup d...@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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: C standard compliance?
From: David Kastrup d...@gnu.org Junio C Hamano gits...@pobox.com writes: David Kastrup d...@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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: C standard compliance?
On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote: Junio C Hamano gits...@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 signature.asc Description: Digital signature
Re: C standard compliance?
brian m. carlson sand...@crustytoothpaste.net writes: On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote: Junio C Hamano gits...@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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
