{"thread":{"id":"19307","subject":"[PATCH] Fix type-punning issues","startedAt":"2009-05-12T01:17:38Z","lastAt":"2009-05-19T07:04:18Z","messageCount":9,"participants":["Dan McGee","Junio C Hamano","Johannes Schindelin","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"113606","messageId":"1242091058-25197-1-git-send-email-dpmcgee@gmail.com","threadId":"19307","inReplyTo":null,"subject":"[PATCH] Fix type-punning issues","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2009-05-12T01:17:38Z","receivedAt":"2009-05-12T01:17:38Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"In these two places we are casting part of our unsigned char sha1 array into\nan unsigned int, which violates GCCs strict-aliasing rules (and probably\nother compilers). In addition, we had two hashing functions defined in\nobject.c. Keep the one function that is \"correct\" and adopt the other ones\nto fit.\n\ndecorate.c: In function ‘hash_obj’:\ndecorate.c:11: warning: dereferencing type-punned pointer will break\nstrict-aliasing rules\n\nSigned-off-by: Dan McGee <dpmcgee@gmail.com>\n---\n\nLet me know if this patch is completely off-base. A quick glance at the\ngenerated assembly seems to show this isn't much of a performance hit,\nespecially given that these functions are inlined anyway. As an FYI the above\nwarning came when compiling with GCC 4.4; I'm not sure if <4.4 showed this\nbehavior.\n\n-Dan\n\n decorate.c |    7 ++++---\n object.c   |   20 +++++++-------------\n 2 files changed, 11 insertions(+), 16 deletions(-)\n\ndiff --git a/decorate.c b/decorate.c\nindex 82d9e22..bf83750 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -8,7 +8,8 @@\n \n static unsigned int hash_obj(const struct object *obj, unsigned int n)\n {\n-\tunsigned int hash = *(unsigned int *)obj->sha1;\n+\tunsigned int hash;\n+\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n \treturn hash % n;\n }\n \n@@ -16,7 +17,7 @@ static void *insert_decoration(struct decoration *n, const struct object *base,\n {\n \tint size = n->size;\n \tstruct object_decoration *hash = n->hash;\n-\tint j = hash_obj(base, size);\n+\tunsigned int j = hash_obj(base, size);\n \n \twhile (hash[j].base) {\n \t\tif (hash[j].base == base) {\n@@ -68,7 +69,7 @@ void *add_decoration(struct decoration *n, const struct object *obj,\n /* Lookup a decoration pointer */\n void *lookup_decoration(struct decoration *n, const struct object *obj)\n {\n-\tint j;\n+\tunsigned int j;\n \n \t/* nothing to lookup */\n \tif (!n->size)\ndiff --git a/object.c b/object.c\nindex 7e6a92c..96ef32d 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,15 +43,16 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n+static unsigned int hash_char(const unsigned char *sha1, unsigned int n)\n {\n-\tunsigned int hash = *(unsigned int *)obj->sha1;\n-\treturn hash % n;\n+\tunsigned int i;\n+\tmemcpy(&i, sha1, sizeof(unsigned int));\n+\treturn (int)(i % n);\n }\n \n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n-\tint j = hash_obj(obj, size);\n+\tunsigned int j = hash_char(obj->sha1, size);\n \n \twhile (hash[j]) {\n \t\tj++;\n@@ -61,22 +62,15 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n \thash[j] = obj;\n }\n \n-static int hashtable_index(const unsigned char *sha1)\n-{\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn (int)(i % obj_hash_size);\n-}\n-\n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tint i;\n+\tunsigned int i;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hashtable_index(sha1);\n+\ti = hash_char(sha1, obj_hash_size);\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n-- \n1.6.2.4\n"},{"id":"113619","messageId":"7vy6t292ix.fsf@alter.siamese.dyndns.org","threadId":"19307","inReplyTo":"1242091058-25197-1-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH] Fix type-punning issues","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-05-12T07:57:42Z","receivedAt":"2009-05-12T07:57:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee <dpmcgee@gmail.com> writes:\n\n> In these two places we are casting part of our unsigned char sha1 array into\n> an unsigned int, which violates GCCs strict-aliasing rules (and probably\n> other compilers).\n\nYay.\n\n>  static unsigned int hash_obj(const struct object *obj, unsigned int n)\n>  {\n> -\tunsigned int hash = *(unsigned int *)obj->sha1;\n> +\tunsigned int hash;\n> +\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n>  \treturn hash % n;\n>  }\n\nI noticed this breakage when I borrowed a friend's FC11 preview (as I\nstill do not have a replacement machine X-<), but didn't manage to spend\nenough time to fix it myself.  I was hoping a way to tell the compiler\nthat this particular pointer usage is Ok in a less hacky way that does not\nupset older compilers, without resorting to low-level memcpy.  But your\nversion to use memcpy() is a literal translation of what the code does,\nand I think it is an acceptable solution.\n\n> @@ -16,7 +17,7 @@ static void *insert_decoration(struct decoration *n, const struct object *base,\n>  {\n>  \tint size = n->size;\n>  \tstruct object_decoration *hash = n->hash;\n> -\tint j = hash_obj(base, size);\n> +\tunsigned int j = hash_obj(base, size);\n\nThese type changes should be Ok, but I would have preferred them to be a\nseparate patch.  From the context, you cannot see if the function in\nplaces outside the patch context uses \"j\" for purposes other than holding\nthe return value of hash_obj() that requires it to be able to hold a\nnetagive value to make sure that this conversion is correct; on the other\nhand, we know n->size is a sane small value that unsigned vs signed int\ndoes not matter, so in that sense making this change in the same patch\nmakes it not about fixing pointer aliasing warning.\n\nBut the code here is correct (I read outside the context).\n\n> @@ -68,7 +69,7 @@ void *add_decoration(struct decoration *n, const struct object *obj,\n>  /* Lookup a decoration pointer */\n>  void *lookup_decoration(struct decoration *n, const struct object *obj)\n>  {\n> -\tint j;\n> +\tunsigned int j;\n\nSame here.\n\n> diff --git a/object.c b/object.c\n> index 7e6a92c..96ef32d 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -43,15 +43,16 @@ int type_from_string(const char *str)\n>  \tdie(\"invalid object type \\\"%s\\\"\", str);\n>  }\n>  \n> -static unsigned int hash_obj(struct object *obj, unsigned int n)\n> +static unsigned int hash_char(const unsigned char *sha1, unsigned int n)\n>  {\n> -\tunsigned int hash = *(unsigned int *)obj->sha1;\n> -\treturn hash % n;\n> +\tunsigned int i;\n> +\tmemcpy(&i, sha1, sizeof(unsigned int));\n> +\treturn (int)(i % n);\n\nHuh?  The original looks the same as the one in decorate.c but why is the\nconversion different?  I am not talking about the difference between hash\nand i, but am wondering about the cast to int (and then back to unsigned\nint by the function signature).\n\nIt might make more sense to have one canonical\n\n\tunsigned int hash_obj(const struct object *obj, unsigned int n)\n\nhere, export it to object.h, and remove the one in decorate.c.\n\nOr am I missing something?\n"},{"id":"113621","messageId":"alpine.DEB.1.00.0905121012430.27348@pacific.mpi-cbg.de","threadId":"19307","inReplyTo":"1242091058-25197-1-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH] Fix type-punning issues","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-05-12T08:13:50Z","receivedAt":"2009-05-12T08:13:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 11 May 2009, Dan McGee wrote:\n\n> In these two places we are casting part of our unsigned char sha1 array \n> into an unsigned int, which violates GCCs strict-aliasing rules (and \n> probably other compilers). In addition, we had two hashing functions \n> defined in object.c. Keep the one function that is \"correct\" and adopt \n> the other ones to fit.\n> \n> decorate.c: In function ‘hash_obj’:\n> decorate.c:11: warning: dereferencing type-punned pointer will break\n> strict-aliasing rules\n\nFWIW we have the same issue in msysGit, having installed GCC 4.4.0 \nrecently, but I did not dare to send my \"fix\".  Yours is much nicer.\n\nThanks,\nDscho"},{"id":"114223","messageId":"449c10960905182132h2c1b38b4jd28721adaeb38484@mail.gmail.com","threadId":"19307","inReplyTo":"7vy6t292ix.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Fix type-punning issues","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2009-05-19T04:32:48Z","receivedAt":"2009-05-19T04:32:48Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Tue, May 12, 2009 at 2:57 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Dan McGee <dpmcgee@gmail.com> writes:\n>\n>> In these two places we are casting part of our unsigned char sha1 array into\n>> an unsigned int, which violates GCCs strict-aliasing rules (and probably\n>> other compilers).\n>\n> Yay.\n>\n\n> It might make more sense to have one canonical\n>\n>        unsigned int hash_obj(const struct object *obj, unsigned int n)\n>\n> here, export it to object.h, and remove the one in decorate.c.\n>\n> Or am I missing something?\n\n(argh: sorry Junio for sending the last reply to just you)\n\nSo due to me taking so long to resubmit, I see you committed a\nstripped-down version of my patch. I had a patch just like this (minus\none newline diff), but it was in a series of 4 I will submit in just a\nsecond.\n\nThe three remaining patches implement the above suggestion of having\none canonical \"hash\" function. However, the name changes to hash_char\nand takes a unsigned char pointer rather than a struct object pointer\nso we can use the same function for both insertion into the hashes as\nwell as lookup.\n\nLooking forward to any feedback.\n\n-Dan\n"},{"id":"114224","messageId":"1242707644-29893-1-git-send-email-dpmcgee@gmail.com","threadId":"19307","inReplyTo":"449c10960905182132h2c1b38b4jd28721adaeb38484@mail.gmail.com","subject":"[PATCH 1/3] Unify signedness in hashing calls","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2009-05-19T04:34:02Z","receivedAt":"2009-05-19T04:34:02Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Our hash_obj and hashtable_index calls and functions were doing a lot of\nfunny things with signedness. Unify all of it to 'unsigned int'.\n\nSigned-off-by: Dan McGee <dpmcgee@gmail.com>\n---\n decorate.c |    4 ++--\n object.c   |    8 ++++----\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/decorate.c b/decorate.c\nindex e6fd8a7..2f8a63e 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -18,7 +18,7 @@ static void *insert_decoration(struct decoration *n, const struct object *base,\n {\n \tint size = n->size;\n \tstruct object_decoration *hash = n->hash;\n-\tint j = hash_obj(base, size);\n+\tunsigned int j = hash_obj(base, size);\n \n \twhile (hash[j].base) {\n \t\tif (hash[j].base == base) {\n@@ -70,7 +70,7 @@ void *add_decoration(struct decoration *n, const struct object *obj,\n /* Lookup a decoration pointer */\n void *lookup_decoration(struct decoration *n, const struct object *obj)\n {\n-\tint j;\n+\tunsigned int j;\n \n \t/* nothing to lookup */\n \tif (!n->size)\ndiff --git a/object.c b/object.c\nindex e1feef9..a6ef439 100644\n--- a/object.c\n+++ b/object.c\n@@ -52,7 +52,7 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)\n \n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n-\tint j = hash_obj(obj, size);\n+\tunsigned int j = hash_obj(obj, size);\n \n \twhile (hash[j]) {\n \t\tj++;\n@@ -62,16 +62,16 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n \thash[j] = obj;\n }\n \n-static int hashtable_index(const unsigned char *sha1)\n+static unsigned int hashtable_index(const unsigned char *sha1)\n {\n \tunsigned int i;\n \tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn (int)(i % obj_hash_size);\n+\treturn i % obj_hash_size;\n }\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tint i;\n+\tunsigned int i;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n-- \n1.6.3.1\n"},{"id":"114226","messageId":"1242707644-29893-2-git-send-email-dpmcgee@gmail.com","threadId":"19307","inReplyTo":"1242707644-29893-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 2/3] Convert hash functions to char instead of struct object","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2009-05-19T04:34:03Z","receivedAt":"2009-05-19T04:34:03Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This will allow us to unify the three hash functions into just one.\n\nSigned-off-by: Dan McGee <dpmcgee@gmail.com>\n---\n decorate.c |    9 ++++-----\n object.c   |    6 +++---\n 2 files changed, 7 insertions(+), 8 deletions(-)\n\ndiff --git a/decorate.c b/decorate.c\nindex 2f8a63e..3c08b96 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -6,11 +6,10 @@\n #include \"object.h\"\n #include \"decorate.h\"\n \n-static unsigned int hash_obj(const struct object *obj, unsigned int n)\n+static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n {\n \tunsigned int hash;\n-\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n+\tmemcpy(&hash, c, sizeof(unsigned int));\n \treturn hash % n;\n }\n \n@@ -18,7 +17,7 @@ static void *insert_decoration(struct decoration *n, const struct object *base,\n {\n \tint size = n->size;\n \tstruct object_decoration *hash = n->hash;\n-\tunsigned int j = hash_obj(base, size);\n+\tunsigned int j = hash_chars(base->sha1, size);\n \n \twhile (hash[j].base) {\n \t\tif (hash[j].base == base) {\n@@ -75,7 +74,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)\n \t/* nothing to lookup */\n \tif (!n->size)\n \t\treturn NULL;\n-\tj = hash_obj(obj, n->size);\n+\tj = hash_chars(obj->sha1, n->size);\n \tfor (;;) {\n \t\tstruct object_decoration *ref = n->hash + j;\n \t\tif (ref->base == obj)\ndiff --git a/object.c b/object.c\nindex a6ef439..09c4d3c 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,16 +43,16 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n+static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n {\n \tunsigned int hash;\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n+\tmemcpy(&hash, c, sizeof(unsigned int));\n \treturn hash % n;\n }\n \n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n-\tunsigned int j = hash_obj(obj, size);\n+\tunsigned int j = hash_chars(obj->sha1, size);\n \n \twhile (hash[j]) {\n \t\tj++;\n-- \n1.6.3.1\n"},{"id":"114225","messageId":"1242707644-29893-3-git-send-email-dpmcgee@gmail.com","threadId":"19307","inReplyTo":"1242707644-29893-2-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 3/3] Unify sha1 char hash functions","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2009-05-19T04:34:04Z","receivedAt":"2009-05-19T04:34:04Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Expose a canonical one in object.c; convert the hashtable_index call and\nthe calls in decorate.c.\n\nSigned-off-by: Dan McGee <dpmcgee@gmail.com>\n---\n decorate.c |    7 -------\n object.c   |   11 ++---------\n object.h   |    1 +\n 3 files changed, 3 insertions(+), 16 deletions(-)\n\ndiff --git a/decorate.c b/decorate.c\nindex 3c08b96..4332924 100644\n--- a/decorate.c\n+++ b/decorate.c\n@@ -6,13 +6,6 @@\n #include \"object.h\"\n #include \"decorate.h\"\n \n-static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n-{\n-\tunsigned int hash;\n-\tmemcpy(&hash, c, sizeof(unsigned int));\n-\treturn hash % n;\n-}\n-\n static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)\n {\n \tint size = n->size;\ndiff --git a/object.c b/object.c\nindex 09c4d3c..34f65e5 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,7 +43,7 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n+unsigned int hash_chars(const unsigned char *c, unsigned int n)\n {\n \tunsigned int hash;\n \tmemcpy(&hash, c, sizeof(unsigned int));\n@@ -62,13 +62,6 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n \thash[j] = obj;\n }\n \n-static unsigned int hashtable_index(const unsigned char *sha1)\n-{\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn i % obj_hash_size;\n-}\n-\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tunsigned int i;\n@@ -77,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hashtable_index(sha1);\n+\ti = hash_chars(sha1, obj_hash_size);\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\ndiff --git a/object.h b/object.h\nindex 89dd0c4..ed73a0a 100644\n--- a/object.h\n+++ b/object.h\n@@ -37,6 +37,7 @@ struct object {\n \n extern const char *typename(unsigned int type);\n extern int type_from_string(const char *str);\n+extern unsigned int hash_chars(const unsigned char *c, unsigned int n);\n \n extern unsigned int get_max_object_index(void);\n extern struct object *get_indexed_object(unsigned int);\n-- \n1.6.3.1\n"},{"id":"114230","messageId":"4A12507A.3050307@viscovery.net","threadId":"19307","inReplyTo":"1242707644-29893-2-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 2/3] Convert hash functions to char instead of struct object","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2009-05-19T06:23:54Z","receivedAt":"2009-05-19T06:23:54Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Dan McGee schrieb:\n> -static unsigned int hash_obj(struct object *obj, unsigned int n)\n> +static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n\nhash_chars suggests that this function hashes arbitrary character\nsequences, but it doesn't do that. Wouldn't hash_object_id be a better\nname? (And the parameter would then obviously be named sha1 or id.)\n\n-- Hannes\n"},{"id":"114233","messageId":"7vk54d8tfx.fsf@alter.siamese.dyndns.org","threadId":"19307","inReplyTo":"4A12507A.3050307@viscovery.net","subject":"Re: [PATCH 2/3] Convert hash functions to char instead of struct object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-05-19T07:04:18Z","receivedAt":"2009-05-19T07:04:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt <j.sixt@viscovery.net> writes:\n\n> Dan McGee schrieb:\n>> -static unsigned int hash_obj(struct object *obj, unsigned int n)\n>> +static unsigned int hash_chars(const unsigned char *c, unsigned int n)\n>\n> hash_chars suggests that this function hashes arbitrary character\n> sequences, but it doesn't do that. Wouldn't hash_object_id be a better\n> name? (And the parameter would then obviously be named sha1 or id.)\n\nYes, the parameter to this function is what we call \"unsigned char *sha1\"\neverywhere else in the code.  hash-object-id or hash-object-name is a good\nname for the function.\n"}]}