From: Chen Xuewei <316403398@qq.com>
It is known that whether the highest bit is extended when char cast to uint32, depends on CPU architecture, which will lead different hash value. This is a fix to accord all architecture behaviour.
Signed-off-by: Chen Xuewei <316403398@qq.com>
---
fix: platform accordance while calculating murmur3
Short Description
=================
fix: platform accordance while calculating murmur3
It is known that whether the highest bit is extended when char cast to
uint32, depends on CPU architecture, which will lead different hash
value. This is a fix to accord all architecture behaviour.
Problem backgroud:
==================
when using git log --max-count=1 <commit> -- <path> in an mixed cpu
cluster environment both arm and x86 in a cluster as a service, where
the <path> character is chinese or some other character that the highest
bit of char is 1. all machines share the same repo disk. It happened
that sometimes you can get the searched file among commit, sometimes you
cannot.
Conditions
==========
1. file path include chinese characters or other characters that the
highest bit is 1.
2. mixed cpu architecture as a git cluster service
Reason
======
when you have over 2 machines (both arm and x86 are included at least
one) as a git server cluster. once you open the commit-graph's
bloom_filter feature. The bloom filter stores the file path as hash
values using the murmur3 function. suppose the arm take it this time,
then the char's highest bit is not extended. for example, on arm,
char(11100110) to uint32(00000000 00000000 00000000 11100110) on x86,
char(11100110) to uint32(11111111 11111111 11111111 11100110) then
according to the murmur3 function that git currently use, the calculated
hash value will be different. If the value was calculated through the
same cpu architure machine, then it is ok. however, sometimes the hash
value is calculated through a different cpu architure machine, then you
cannot get the searched file. for example, bloom_filter's hash set is
calculated through arm, and query through x86. So the hash value is
incorrect, then missed the searched file.
Solution
========
No matter what the highest 24 bits will be when char cast to uint32, the
murmur3 function only cares about the char part , which is only the
lowest 8 bits, so we can use & 0xFF(11111111) to the casted uint32 value
to choose only the lowest 8 bits.
Others
======
after fixed the bug, the historical bloom_filter data stored in
commit-graph need to be updated. because the path's hash value is
already calculated through a bad way. so we need to update it. this need
to be done in repositoryPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1636%2Fcdegree%2Fmaster-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1636/cdegree/master-v1 Pull-Request: https://github.com/git/git/pull/1636
bloom.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
Show changes to bloom.c +5 −5
diff --git a/bloom.c b/bloom.c index 1474aa19fa5..bc40edac795 100644 --- a/bloom.c +++ b/bloom.c @@ -116,11 +116,11 @@ uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) uint32_t k; for (i = 0; i < len4; i++) { - uint32_t byte1 = (uint32_t)data[4*i]; - uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8; - uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16; - uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24; - k = byte1 | byte2 | byte3 | byte4; + uint32_t byte1 = ((uint32_t)data[4*i]) & 0xFF; + uint32_t byte2 = ((uint32_t)data[4*i + 1]) & 0xFF; + uint32_t byte3 = ((uint32_t)data[4*i + 2]) & 0xFF; + uint32_t byte4 = ((uint32_t)data[4*i + 3]) & 0xFF; + k = byte1 | (byte2 << 8) | (byte3 << 16) | (byte4 << 24); k *= c1; k = rotate_left(k, r1); k *= c2; base-commit: a26002b62827b89a19b1084bd75d9371d565d03c
-- gitgitgadget
