{"thread":{"id":"60685","subject":"[PATCH] fix: platform accordance while calculating murmur3","startedAt":"2024-01-04T13:56:50Z","lastAt":"2024-01-04T18:27:51Z","messageCount":4,"participants":["Chen Xuewei via GitGitGadget","Taylor Blau","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"486291","messageId":"pull.1636.git.git.1704376606625.gitgitgadget@gmail.com","threadId":"60685","inReplyTo":null,"subject":"[PATCH] fix: platform accordance while calculating murmur3","fromName":"Chen Xuewei via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-01-04T13:56:46Z","receivedAt":"2024-01-04T13:56:50Z","isPatch":true,"sender":{"key":"name:Chen Xuewei","avatar":null},"body":"From: Chen Xuewei <316403398@qq.com>\n\nIt is known that whether the highest bit is extended when char cast to\nuint32, depends on CPU architecture, which will lead different hash\nvalue. This is a fix to accord all architecture behaviour.\n\nSigned-off-by: Chen Xuewei <316403398@qq.com>\n---\n    fix: platform accordance while calculating murmur3\n    \n    \n    Short Description\n    =================\n    \n    fix: platform accordance while calculating murmur3\n    \n    It is known that whether the highest bit is extended when char cast to\n    uint32, depends on CPU architecture, which will lead different hash\n    value. This is a fix to accord all architecture behaviour.\n    \n    \n    Problem backgroud:\n    ==================\n    \n    when using git log --max-count=1 <commit> -- <path> in an mixed cpu\n    cluster environment both arm and x86 in a cluster as a service, where\n    the <path> character is chinese or some other character that the highest\n    bit of char is 1. all machines share the same repo disk. It happened\n    that sometimes you can get the searched file among commit, sometimes you\n    cannot.\n    \n    \n    Conditions\n    ==========\n    \n     1. file path include chinese characters or other characters that the\n        highest bit is 1.\n     2. mixed cpu architecture as a git cluster service\n    \n    \n    Reason\n    ======\n    \n    when you have over 2 machines (both arm and x86 are included at least\n    one) as a git server cluster. once you open the commit-graph's\n    bloom_filter feature. The bloom filter stores the file path as hash\n    values using the murmur3 function. suppose the arm take it this time,\n    then the char's highest bit is not extended. for example, on arm,\n    char(11100110) to uint32(00000000 00000000 00000000 11100110) on x86,\n    char(11100110) to uint32(11111111 11111111 11111111 11100110) then\n    according to the murmur3 function that git currently use, the calculated\n    hash value will be different. If the value was calculated through the\n    same cpu architure machine, then it is ok. however, sometimes the hash\n    value is calculated through a different cpu architure machine, then you\n    cannot get the searched file. for example, bloom_filter's hash set is\n    calculated through arm, and query through x86. So the hash value is\n    incorrect, then missed the searched file.\n    \n    \n    Solution\n    ========\n    \n    No matter what the highest 24 bits will be when char cast to uint32, the\n    murmur3 function only cares about the char part , which is only the\n    lowest 8 bits, so we can use & 0xFF(11111111) to the casted uint32 value\n    to choose only the lowest 8 bits.\n    \n    \n    Others\n    ======\n    \n    after fixed the bug, the historical bloom_filter data stored in\n    commit-graph need to be updated. because the path's hash value is\n    already calculated through a bad way. so we need to update it. this need\n    to be done in repository\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1636%2Fcdegree%2Fmaster-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1636/cdegree/master-v1\nPull-Request: https://github.com/git/git/pull/1636\n\n bloom.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 1474aa19fa5..bc40edac795 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -116,11 +116,11 @@ uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n \n \tuint32_t k;\n \tfor (i = 0; i < len4; i++) {\n-\t\tuint32_t byte1 = (uint32_t)data[4*i];\n-\t\tuint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;\n-\t\tuint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;\n-\t\tuint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;\n-\t\tk = byte1 | byte2 | byte3 | byte4;\n+\t\tuint32_t byte1 = ((uint32_t)data[4*i]) & 0xFF;\n+\t\tuint32_t byte2 = ((uint32_t)data[4*i + 1]) & 0xFF;\n+\t\tuint32_t byte3 = ((uint32_t)data[4*i + 2]) & 0xFF;\n+\t\tuint32_t byte4 = ((uint32_t)data[4*i + 3]) & 0xFF;\n+\t\tk = byte1 | (byte2 << 8) | (byte3 << 16) | (byte4 << 24);\n \t\tk *= c1;\n \t\tk = rotate_left(k, r1);\n \t\tk *= c2;\n\nbase-commit: a26002b62827b89a19b1084bd75d9371d565d03c\n-- \ngitgitgadget\n"},{"id":"486293","messageId":"ZZbGZYhhWpHh2pS/@nand.local","threadId":"60685","inReplyTo":"pull.1636.git.git.1704376606625.gitgitgadget@gmail.com","subject":"Re: [PATCH] fix: platform accordance while calculating murmur3","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-04T14:53:25Z","receivedAt":"2024-01-04T14:53:27Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Chen,\n\nOn Thu, Jan 04, 2024 at 01:56:46PM +0000, Chen Xuewei via GitGitGadget wrote:\n> From: Chen Xuewei <316403398@qq.com>\n>\n> It is known that whether the highest bit is extended when char cast to\n> uint32, depends on CPU architecture, which will lead different hash\n> value. This is a fix to accord all architecture behaviour.\n\nThanks for your patch. A similar fix is being pursued in [1], part of\nwhich includes [2], which I believe is functionally equivalent to your\npatch here.\n\n>     Others\n>     ======\n>\n>     after fixed the bug, the historical bloom_filter data stored in\n>     commit-graph need to be updated. because the path's hash value is\n>     already calculated through a bad way. so we need to update it. this need\n>     to be done in repository\n\nWe would not want to impose that burden on all users upon upgrading to\nthe latest Git version. In [1] we are perusing an approach where:\n\n  - The Bloom data is stored with a version identifier, meaning that we\n    can still use the existing/non-murmur3 Bloom filters after\n    upgrading.\n\n  - When the user decides to upgrade from v1 -> v2 Bloom filters, we\n    reuse the existing Bloom filter data when possible, namely when all\n    paths within a tree have no non-ASCII characters.\n\nIf you have thoughts on the approach in [1], they would be most welcome.\n\nThanks,\nTaylor\n\n[1]: https://lore.kernel.org/git/cover.1697653929.git.me@ttaylorr.com/\n[2]: https://lore.kernel.org/git/f6ab427ead86bc82284b2c721f3c177947ece3c9.1697653929.git.me@ttaylorr.com/\n"},{"id":"486300","messageId":"xmqq7ckp7ysl.fsf@gitster.g","threadId":"60685","inReplyTo":"pull.1636.git.git.1704376606625.gitgitgadget@gmail.com","subject":"Re: [PATCH] fix: platform accordance while calculating murmur3","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-01-04T18:12:42Z","receivedAt":"2024-01-04T18:12:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Chen Xuewei via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Chen Xuewei <316403398@qq.com>\n>\n> It is known that whether the highest bit is extended when char cast to\n> uint32, depends on CPU architecture, which will lead different hash\n> value. This is a fix to accord all architecture behaviour.\n>\n> Signed-off-by: Chen Xuewei <316403398@qq.com>\n> ---\n\nJonathan and Taylor, isn't this what you two were working together\non?  How would we want to proceed?\n\nChen, using the right implementation of the hash function to be used\nafter the next rebuild of the Bloom data has so far been treated as\nonly one part of the solution (the others include \"how to deal with\nthe existing data?  do we have a way to tell our binary to safely\nignore the Bloom data using a wrong hash?\" and \"how to make sure old\nbinaries do not get confused by the Bloom data using the right/new\nhash?\").\n\nJonathan and Taylor's (stalled) effort is here\n\n    https://lore.kernel.org/git/cover.1697653929.git.me@ttaylorr.com\n\n\nThanks.\n\n\n\n"},{"id":"486302","messageId":"ZZb4pN/zR12m93L4@nand.local","threadId":"60685","inReplyTo":"xmqq7ckp7ysl.fsf@gitster.g","subject":"Re: [PATCH] fix: platform accordance while calculating murmur3","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-04T18:27:48Z","receivedAt":"2024-01-04T18:27:51Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Jan 04, 2024 at 10:12:42AM -0800, Junio C Hamano wrote:\n> Jonathan and Taylor, isn't this what you two were working together\n> on?  How would we want to proceed?\n\nThey are indeed similar. I think that Jonathan and my series would\nsupersede this effort.\n\nBut I would appreciate if Chen took a look at the approach in that\nseries to make sure that we're all on the same page and that Jonathan\nand I aren't missing anything.\n\nThanks,\nTaylor\n"}]}