{"thread":{"id":"59730","subject":"Changed path filter hash differs from murmur3 if char is signed","startedAt":"2023-05-11T22:41:13Z","lastAt":"2023-05-12T21:28:10Z","messageCount":7,"participants":["Jonathan Tan","Junio C Hamano","Taylor Blau"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"477101","messageId":"20230511224101.972442-1-jonathantanmy@google.com","threadId":"59730","inReplyTo":null,"subject":"Changed path filter hash differs from murmur3 if char is signed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-05-11T22:40:59Z","receivedAt":"2023-05-11T22:41:13Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This issue arose while I was implementing changed path filters (the\nbloom filters in the commit graph file) for JGit [1].\n\nIt turns out that if a repository contains paths that have at least one\ncharacter greater than 0x7f, Git writes these filters and interprets\nthem (when read from the commit graph file) differently depending on\nwhether \"char\" is signed or unsigned, and when \"char\" is signed (this\ncan be controlled by a compiler flag), the implementation of the murmur3\nhash differs from the one in Wikipedia and elsewhere. (I looked into\nGit's Makefile and didn't see anything that controlled whether \"char\"\nis signed, so I presume that the default of the compiler used applies.)\nThis can be seen from the murmur3_seeded() function in bloom.c:\n\n> uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n> {\n[snip]\n> \t\tuint32_t byte1 = (uint32_t)data[4*i];\n\nNote that data[4*i] is of type \"char\". When I first read this, I thought\nthat no sign extension would occur regardless of the signedness of char\n(that is, (uint32_t)(signed char)-1 == (uint32_t)(unsigned char)-1)\nbut it turns out that sign extension does occur if the thing being cast\nis signed (that is, (uint32_t)(signed char)-1 != (uint32_t)(unsigned\nchar)-1) [2]. The implementation of the murmur3 hash in Wikipedia (and\npresumably the intention of the author here, since the variable is named\n\"byte1\") expects this value to not exceed 0xff, but this is not the case\nif sign extension occurs.\n\nI looked if this was discussed at the time this patch was presented [3]\nbut couldn't find anything related.\n\nSo...how do we proceed? I can see at least 2 ways:\n\n - Decide that we're going to stick with the details of the existing\n   implementation and declare that \"data\" is always interpreted as signed.\n   In that case, I would put \"signed\" wherever necessary, rename the\n   function to something that is not \"murmur3\", and change the names of\n   byte1 etc. to indicate that they are not constrained to be less than or\n   equal to 0xff.\n\n - Bump the version number to 2 and correct the implementation to\n   match murmur3 (so, \"data\" is unsigned). Then we would have to think of\n   a transition plan. One possible one might be to always reject version\n   1 bloom filters, which I'm personally OK with, but it may seem too\n   heavy a cost to some since in the perhaps typical case where a repo has\n   filenames restricted to 0x7f and below, the existing bloom filters are\n   still correct.\n\nOf the two, I prefer the latter, but I'm open to suggestions.\n\n[1] https://git.eclipse.org/r/c/jgit/jgit/+/201851/2\n[2] Verified in practice and also prescribed by the C standard; see\n  e.g. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf section\n  6.3.1.3 point 2.\n[3] https://lore.kernel.org/git/a5aa3415c05ee9bc67a9471445a20c71a9834673.1586192395.git.gitgitgadget@gmail.com/\n\n\n"},{"id":"477103","messageId":"xmqqjzxetrbv.fsf@gitster.g","threadId":"59730","inReplyTo":"20230511224101.972442-1-jonathantanmy@google.com","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-11T22:51:16Z","receivedAt":"2023-05-11T22:51:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> So...how do we proceed? I can see at least 2 ways:\n>\n>  - Decide that we're going to stick with the details of the existing\n>    implementation and declare that \"data\" is always interpreted as signed.\n>    In that case, I would put \"signed\" wherever necessary, rename the\n>    function to something that is not \"murmur3\", and change the names of\n>    byte1 etc. to indicate that they are not constrained to be less than or\n>    equal to 0xff.\n>\n>  - Bump the version number to 2 and correct the implementation to\n>    match murmur3 (so, \"data\" is unsigned). Then we would have to think of\n>    a transition plan. One possible one might be to always reject version\n>    1 bloom filters, which I'm personally OK with, but it may seem too\n>    heavy a cost to some since in the perhaps typical case where a repo has\n>    filenames restricted to 0x7f and below, the existing bloom filters are\n>    still correct.\n\nIf path filter hashing were merely advisory, in the sense that if a\nmatching data is found, great, the processing goes faster, but if\nnot, we would get correct results albeit not so quickly, a third\noption would be to just update the implementation without updating\nthe version number.  But we may not be so lucky---you must have seen\na wrong result returned quickly, which is not what we want to see.\n\nBut if I recall correctly we made the file format in such a way that\nbumping the version number is cheap in that transition can appear\nseamless.  An updated implementation can just be told to _ignore_\nold and possibly incorrect Bloom filters until it gets told to\nrecompute, at which time it can write a correct one with a new\nversion number.  So I would prefer your \"Bump the version number and\nignore the old and possibly wrong data\".\n\nThanks.\n"},{"id":"477104","messageId":"ZF116EDcmAy7XEbC@nand.local","threadId":"59730","inReplyTo":"xmqqjzxetrbv.fsf@gitster.g","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-11T23:10:32Z","receivedAt":"2023-05-11T23:10:37Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, May 11, 2023 at 03:51:16PM -0700, Junio C Hamano wrote:\n> Jonathan Tan <jonathantanmy@google.com> writes:\n>\n> > So...how do we proceed? I can see at least 2 ways:\n> >\n> >  - Decide that we're going to stick with the details of the existing\n> >    implementation and declare that \"data\" is always interpreted as signed.\n> >    In that case, I would put \"signed\" wherever necessary, rename the\n> >    function to something that is not \"murmur3\", and change the names of\n> >    byte1 etc. to indicate that they are not constrained to be less than or\n> >    equal to 0xff.\n> >\n> >  - Bump the version number to 2 and correct the implementation to\n> >    match murmur3 (so, \"data\" is unsigned). Then we would have to think of\n> >    a transition plan. One possible one might be to always reject version\n> >    1 bloom filters, which I'm personally OK with, but it may seem too\n> >    heavy a cost to some since in the perhaps typical case where a repo has\n> >    filenames restricted to 0x7f and below, the existing bloom filters are\n> >    still correct.\n>\n> If path filter hashing were merely advisory, in the sense that if a\n> matching data is found, great, the processing goes faster, but if\n> not, we would get correct results albeit not so quickly, a third\n> option would be to just update the implementation without updating\n> the version number.  But we may not be so lucky---you must have seen\n> a wrong result returned quickly, which is not what we want to see.\n\nRight; from my understanding of Jonathan's message, I believe that we\nwould get the wrong results if the implementation of not-quite-murmur3\nwere corrected without updating the on-disk Bloom filters.\n\nWe already have the bloom_filter_settings struct, which could also\nencode whether or not the data was computed with sign extension or not.\nIf we are consistent in computing the hashes when we write Bloom filters\nand when we re-compute hashes to query them, I'd think we would be able\nto reuse the existing filters.\n\nThat would be nice to do if we could. Unfortunately, I don't think there\nis an easy way to determine the signed-ness of an existing set of Bloom\nfilters, nor a guarantee that they all have the same signed-ness (IOW,\nthe Bloom filters could have been built up across multiple copies of\nGit, each with different compiler settings).\n\nSo I'm not sure that that is a productive direction for us to take.\n\n> But if I recall correctly we made the file format in such a way that\n> bumping the version number is cheap in that transition can appear\n> seamless.  An updated implementation can just be told to _ignore_\n> old and possibly incorrect Bloom filters until it gets told to\n> recompute, at which time it can write a correct one with a new\n> version number.  So I would prefer your \"Bump the version number and\n> ignore the old and possibly wrong data\".\n\nVersion numbers are easy to increment, as is the case when adding new\nchunks to the chunked file format used by commit-graph,\nmulti-pack-index, etc.\n\nHowever, computing Bloom filters en-masse from scratch is fairly\nexpensive. At GitHub when we were rolling out Bloom filters to all\nrepositories a few years ago, I wrote 809e0327f5\n(builtin/commit-graph.c: introduce '--max-new-filters=<n>', 2020-09-18)\nto avoid spending too much time computing new filters from scratch.\n\nIf we do have to re-compute all of the filters from scratch, it may be\nworth considering enumerating all of the repository's paths first and\nseeing if any of them are >0xff. If none are, we can propagate the\nexisting filters forward without having to compute new ones.\n\nBetter yet, we should be able to reuse existing Bloom filter data for\npaths that have all characters <=0xff, and only recompute them where\nnecessary. That makes much more sense than the previous paragraph.\n\nThanks,\nTaylor\n"},{"id":"477198","messageId":"20230512173330.1072880-1-jonathantanmy@google.com","threadId":"59730","inReplyTo":"ZF116EDcmAy7XEbC@nand.local","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-05-12T17:33:29Z","receivedAt":"2023-05-12T17:33:43Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> On Thu, May 11, 2023 at 03:51:16PM -0700, Junio C Hamano wrote:\n> > If path filter hashing were merely advisory, in the sense that if a\n> > matching data is found, great, the processing goes faster, but if\n> > not, we would get correct results albeit not so quickly, a third\n> > option would be to just update the implementation without updating\n> > the version number.  But we may not be so lucky---you must have seen\n> > a wrong result returned quickly, which is not what we want to see.\n> \n> Right; from my understanding of Jonathan's message, I believe that we\n> would get the wrong results if the implementation of not-quite-murmur3\n> were corrected without updating the on-disk Bloom filters.\n\nYes - if the bloom filter contained junk data (in our example, created\nusing a different hash function on filenames that have characters that\nexceed 0x7f), the bloom filter would report \"no, this commit does not\ncontain a change in such-and-such path\" and then we would skip the\ncommit, even if the commit did have a change in that path.\n\n> We already have the bloom_filter_settings struct, which could also\n> encode whether or not the data was computed with sign extension or not.\n> If we are consistent in computing the hashes when we write Bloom filters\n> and when we re-compute hashes to query them, I'd think we would be able\n> to reuse the existing filters.\n> \n> That would be nice to do if we could. Unfortunately, I don't think there\n> is an easy way to determine the signed-ness of an existing set of Bloom\n> filters, nor a guarantee that they all have the same signed-ness (IOW,\n> the Bloom filters could have been built up across multiple copies of\n> Git, each with different compiler settings).\n> \n> So I'm not sure that that is a productive direction for us to take.\n\nAgreed.\n\n> > But if I recall correctly we made the file format in such a way that\n> > bumping the version number is cheap in that transition can appear\n> > seamless.  An updated implementation can just be told to _ignore_\n> > old and possibly incorrect Bloom filters until it gets told to\n> > recompute, at which time it can write a correct one with a new\n> > version number.  So I would prefer your \"Bump the version number and\n> > ignore the old and possibly wrong data\".\n> \n> Version numbers are easy to increment, as is the case when adding new\n> chunks to the chunked file format used by commit-graph,\n> multi-pack-index, etc.\n> \n> However, computing Bloom filters en-masse from scratch is fairly\n> expensive. At GitHub when we were rolling out Bloom filters to all\n> repositories a few years ago, I wrote 809e0327f5\n> (builtin/commit-graph.c: introduce '--max-new-filters=<n>', 2020-09-18)\n> to avoid spending too much time computing new filters from scratch.\n\nThanks for this pointer.\n\n> If we do have to re-compute all of the filters from scratch, it may be\n> worth considering enumerating all of the repository's paths first and\n> seeing if any of them are >0xff. If none are, we can propagate the\n> existing filters forward without having to compute new ones.\n\nOne way server operators can do this is by:\n - patching their Git to ignore the bloom filter version number\n - in a batch job, enumerate all trees and see their filenames\n - for the repos that have <=0x7f filenames, bump version number\n - update Git to the latest version (that uses the new hash)\n\nEnumerating all trees saves on revision walking, which hopefully will\nspeed things up.\n\nI don't have statistics on this, but if the majority of repos have\nonly <=0x7f filenames (which seems reasonable to me), this might save\nsufficient work that we can proceed with bumping the version number and\nignoring old data.\n\n> Better yet, we should be able to reuse existing Bloom filter data for\n> paths that have all characters <=0xff, and only recompute them where\n> necessary. That makes much more sense than the previous paragraph.\n\nI would think that at the point that we know the paths that have been\nchanged for a commit, the cost of computation of the bloom filter (all\nin the CPU) is negligible compared to the I/O it took for us to retrieve\nall the paths (so the solution of just ignoring old data seems better\nto me). But perhaps at large scales, we do want to save the computation\ntime anyway.\n"},{"id":"477208","messageId":"xmqqbkippca5.fsf@gitster.g","threadId":"59730","inReplyTo":"20230512173330.1072880-1-jonathantanmy@google.com","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-12T19:42:10Z","receivedAt":"2023-05-12T19:42:25Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> Yes - if the bloom filter contained junk data (in our example, created\n> using a different hash function on filenames that have characters that\n> exceed 0x7f), the bloom filter would report \"no, this commit does not\n> contain a change in such-and-such path\" and then we would skip the\n> commit, even if the commit did have a change in that path.\n\nJust to help my understanding (read: I am not suggesting this as one\nof the holes to exploit to help a smooth transition), does the above\nmean that, as long as the path we are asking about does not have a\nbyte with the high-bit set, we would be OK, even if the Bloom filter\nwere constructed with a bad function and there were other paths that\nhad such a byte?\n\n> I don't have statistics on this, but if the majority of repos have\n> only <=0x7f filenames (which seems reasonable to me), this might save\n> sufficient work that we can proceed with bumping the version number and\n> ignoring old data.\n>\n>> Better yet, we should be able to reuse existing Bloom filter data for\n>> paths that have all characters <=0xff, and only recompute them where\n\n\"ff\" -> \"7f\" I presume?\n\n>> necessary. That makes much more sense than the previous paragraph.\n"},{"id":"477215","messageId":"20230512205427.1090937-1-jonathantanmy@google.com","threadId":"59730","inReplyTo":"xmqqbkippca5.fsf@gitster.g","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-05-12T20:54:27Z","receivedAt":"2023-05-12T20:54:35Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n> Jonathan Tan <jonathantanmy@google.com> writes:\n> \n> > Yes - if the bloom filter contained junk data (in our example, created\n> > using a different hash function on filenames that have characters that\n> > exceed 0x7f), the bloom filter would report \"no, this commit does not\n> > contain a change in such-and-such path\" and then we would skip the\n> > commit, even if the commit did have a change in that path.\n> \n> Just to help my understanding (read: I am not suggesting this as one\n> of the holes to exploit to help a smooth transition), does the above\n> mean that, as long as the path we are asking about does not have a\n> byte with the high-bit set, we would be OK, even if the Bloom filter\n> were constructed with a bad function and there were other paths that\n> had such a byte?\n\nAh, thanks for asking. Yes, the false negative I describe above only\nhappens when the path we're querying for contains a character >0x7f (so\nif there is no byte with the high-bit set, it is still OK).\n\n> > I don't have statistics on this, but if the majority of repos have\n> > only <=0x7f filenames (which seems reasonable to me), this might save\n> > sufficient work that we can proceed with bumping the version number and\n> > ignoring old data.\n> >\n> >> Better yet, we should be able to reuse existing Bloom filter data for\n> >> paths that have all characters <=0xff, and only recompute them where\n> \n> \"ff\" -> \"7f\" I presume?\n\nThat was my assumption too, but Taylor can clarify.\n"},{"id":"477220","messageId":"ZF6vW7/BhKqUyP7R@nand.local","threadId":"59730","inReplyTo":"20230512205427.1090937-1-jonathantanmy@google.com","subject":"Re: Changed path filter hash differs from murmur3 if char is signed","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-12T21:27:55Z","receivedAt":"2023-05-12T21:28:10Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 12, 2023 at 01:54:27PM -0700, Jonathan Tan wrote:\n> > > I don't have statistics on this, but if the majority of repos have\n> > > only <=0x7f filenames (which seems reasonable to me), this might save\n> > > sufficient work that we can proceed with bumping the version number and\n> > > ignoring old data.\n> > >\n> > >> Better yet, we should be able to reuse existing Bloom filter data for\n> > >> paths that have all characters <=0xff, and only recompute them where\n> >\n> > \"ff\" -> \"7f\" I presume?\n>\n> That was my assumption too, but Taylor can clarify.\n\nSorry, yes, I meant \"0x7f\" here not \"0xff\". Thanks for catching, both.\n\nThanks,\nTaylor\n"}]}