{"thread":{"id":"35759","subject":"C standard compliance?","startedAt":"2014-01-29T20:33:08Z","lastAt":"2014-01-30T00:02:20Z","messageCount":6,"participants":["David Kastrup","Junio C Hamano","Philip Oakley","brian m. carlson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"233902","messageId":"87iot25y0r.fsf@fencepost.gnu.org","threadId":"35759","inReplyTo":null,"subject":"C standard compliance?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-29T20:33:08Z","receivedAt":"2014-01-29T20:33:08Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nHi, I am wondering if I may compare pointers with < that have been\ncreated using different calls of malloc.\n\nThe C standard does not allow this (inequalities are only allowed for\npointers into the same structure) to allow for some cheapskate sort of\ncomparison in segmented architectures.\n\nNow of course being able to _sort_ pointers also allows to _collate_\nthem. It totally does not matter just _what_ their ordering relation is\nas long as it yields to a sorting function (namely obeys some basic\nrelations).\n\nThe question is whether this kind of undefined behavior (which almost\nnever is implemented in unexpected ways) is frowned upon in the Git\ncodebase or not.\n\n-- \nDavid Kastrup\n"},{"id":"233903","messageId":"xmqqwqhiikpg.fsf@gitster.dls.corp.google.com","threadId":"35759","inReplyTo":"87iot25y0r.fsf@fencepost.gnu.org","subject":"Re: C standard compliance?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-29T20:42:19Z","receivedAt":"2014-01-29T20:42:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Hi, I am wondering if I may compare pointers with < that have been\n> created using different calls of malloc.\n>\n> The C standard does not allow this (inequalities are only allowed for\n> pointers into the same structure) to allow for some cheapskate sort of\n> comparison in segmented architectures.\n\nHmm... if you were to implement a set of pointers in such a way that\nyou can cheaply tell if an unknown pointer belongs to that set, you\nwould use a hashtable, keyed with something that is derived from the\nvalue of the pointer casted to uintptr_t, I would think. Is such a\nuse of ((uintptr_t)ptr) unallowed? If it is allowed, comparing two\nunrelated pointers after casting them to uintptr_t would equally be\nvalid, I would have to think.\n"},{"id":"233904","messageId":"87eh3q5x42.fsf@fencepost.gnu.org","threadId":"35759","inReplyTo":"xmqqwqhiikpg.fsf@gitster.dls.corp.google.com","subject":"Re: C standard compliance?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-29T20:52:45Z","receivedAt":"2014-01-29T20:52:45Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Hi, I am wondering if I may compare pointers with < that have been\n>> created using different calls of malloc.\n>>\n>> The C standard does not allow this (inequalities are only allowed for\n>> pointers into the same structure) to allow for some cheapskate sort of\n>> comparison in segmented architectures.\n>\n> Hmm... if you were to implement a set of pointers in such a way that\n> you can cheaply tell if an unknown pointer belongs to that set, you\n> would use a hashtable, keyed with something that is derived from the\n> value of the pointer casted to uintptr_t, I would think.\n\nThe types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999\n(C99). So it would seem that I'd be covering fewer cases rather than\nmore in that manner.\n\nI should think that architectures providing uintptr_t/intptr_t would\nhave very little incentive _not_ to offer pointer inequalities\nequivalent to either the uintptr_t or intptr_t type conversion.\n\n-- \nDavid Kastrup\n"},{"id":"233908","messageId":"3B29F809B09A46B38D4873721D0CCF06@PhilipOakley","threadId":"35759","inReplyTo":"87eh3q5x42.fsf@fencepost.gnu.org","subject":"Re: C standard compliance?","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2014-01-29T22:21:34Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"David Kastrup\" \n> Junio C Hamano writes:\n>\n>> David Kastrup writes:\n>>\n>>> Hi, I am wondering if I may compare pointers with < that have been\n>>> created using different calls of malloc.\n>>>\n>>> The C standard does not allow this (inequalities are only allowed\n>>> for\n>>> pointers into the same structure) to allow for some cheapskate sort\n>>> of\n>>> comparison in segmented architectures.\n>>\n>> Hmm... if you were to implement a set of pointers in such a way that\n>> you can cheaply tell if an unknown pointer belongs to that set, you\n>> would use a hashtable, keyed with something that is derived from the\n>> value of the pointer casted to uintptr_t, I would think.\n>\n> The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999\n> (C99). So it would seem that I'd be covering fewer cases rather than\n> more in that manner.\n>\n> I should think that architectures providing uintptr_t/intptr_t would\n> have very little incentive _not_ to offer pointer inequalities\n> equivalent to either the uintptr_t or intptr_t type conversion.\n>\nUndefined behaviours become hidden bugs of the future...\nhttp://article.gmane.org/gmane.comp.version-control.git/230583\n\n\"blog on the problems of unexpected optimization bugs,\nsuch as dereferencing a null pointer. \"Finding Undefined Behavior Bugs\nby Finding Dead Code\" http://blog.regehr.org/archives/970 which links to\nthe draft of an interesting paper\nhttp://pdos.csail.mit.edu/~xi/papers/stack-sosp13.pdf\"\n\nThe code has now been released http://css.csail.mit.edu/stack/\nhttps://github.com/xiw/stack/, and a few potential errors in Git were \ncaught by that tool by Stefan Beller.\n\nThe key point of the paper was never to try to use an 'obvious', but\nundefined, behaviour.\n\n--\nPhilip\n"},{"id":"233909","messageId":"20140129233321.GC91854@vauxhall.crustytoothpaste.net","threadId":"35759","inReplyTo":"87eh3q5x42.fsf@fencepost.gnu.org","subject":"Re: C standard compliance?","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2014-01-29T23:33:21Z","receivedAt":"2014-01-29T23:33:21Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote:\n> Junio C Hamano writes:\n> > Hmm... if you were to implement a set of pointers in such a way that\n> > you can cheaply tell if an unknown pointer belongs to that set, you\n> > would use a hashtable, keyed with something that is derived from the\n> > value of the pointer casted to uintptr_t, I would think.\n> \n> The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999\n> (C99). So it would seem that I'd be covering fewer cases rather than\n> more in that manner.\n\nI think we already use uintptr_t in the codebase, and if it's not\npresent, we typedef it to unsigned long. So I think it should be fine\n(and well-defined) if instead of doing\n\n void *p, *q;\n ...\n if (p < q)\n ...\n\nyou do:\n\n void *p, *q;\n ...\n if ((uintptr_t)p < (uintptr_t)q)\n ...\n\nThen on those systems where the compiler has some bizarre undefined\nbehavior checking, the code will work. On systems that don't have\nuintptr_t, the compiler is probably not smart enough to perform such a\ncheck anyway.\n\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"233911","messageId":"877g9i5oc3.fsf@fencepost.gnu.org","threadId":"35759","inReplyTo":"20140129233321.GC91854@vauxhall.crustytoothpaste.net","subject":"Re: C standard compliance?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-30T00:02:20Z","receivedAt":"2014-01-30T00:02:20Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\"brian m. carlson\" writes:\n\n> On Wed, Jan 29, 2014 at 09:52:45PM +0100, David Kastrup wrote:\n>> Junio C Hamano writes:\n>> > Hmm... if you were to implement a set of pointers in such a way that\n>> > you can cheaply tell if an unknown pointer belongs to that set, you\n>> > would use a hashtable, keyed with something that is derived from the\n>> > value of the pointer casted to uintptr_t, I would think.\n>> \n>> The types intptr_t and uintptr_t are optional in ISO/IEC 9899:1999\n>> (C99). So it would seem that I'd be covering fewer cases rather than\n>> more in that manner.\n>\n> I think we already use uintptr_t in the codebase, and if it's not\n> present, we typedef it to unsigned long. So I think it should be fine\n> (and well-defined) if instead of doing\n>\n> void *p, *q;\n> ...\n> if (p < q)\n> ...\n>\n> you do:\n>\n> void *p, *q;\n> ...\n> if ((uintptr_t)p < (uintptr_t)q)\n> ...\n>\n> Then on those systems where the compiler has some bizarre undefined\n> behavior checking, the code will work. On systems that don't have\n> uintptr_t, the compiler is probably not smart enough to perform such a\n> check anyway.\n\nThe use case is actually sorting a list such that entries pointing to\nthe same malloced \"origin\" data structure are in adjacent list\npositions. At list intptr_t seems used plentifully in Git.\n\n-- \nDavid Kastrup\n"}]}