[Bug] CRITICAL - INCORRECT HASH CALCULATION

[VbhvGupta]

mono/mono/eglib/ghashtable.c

Lines 676 to 680 in 0f53e9e

	unsigned char *p = (unsigned char *) v1;
	while (*p++)
	hash = (hash << 5) - (hash + *p);

The *p++ increment happens before the hash calculation, so when *p is referenced inside the loop, Its actually looking at the character after the one that was just tested.

This means:

• The first character of the string is never hashed
• We are hashing one character past where we should be (potentially garbage memory after the null terminator)

Any two UTF‑8 strings that only differ in their initial character (e.g., "abc" vs. "xbc") will therefore produce identical hash values and single‑character strings hash to zero.

[madewokherd]

The code looks correct to me. p++ is post-increment so the expression returns the value of p before it's changed.

Reopen if you have a test case for this.

[madewokherd]

Whoops, misread. The point about hashing outside the string is incorrect, though. When p++ returns 0, and p is incremented past the end of the string, the loop will terminate instead of accessing p.

So this will produce hash collisions, which at most will have a performance impact. Given that the performance impact hasn't been noticed, this particular function is only used by the runtime and not the class libraries, and for those limited cases two strings differing by only one character is probably uncommon, I'd say this is only a minor issue.

[VbhvGupta]

The code looks correct to me. p++ is post-increment so the expression returns the value of p before it's changed.

Reopen if you have a test case for this.

In the condition while (*p++) , *p++ is parsed as *(p++). It tests the current byte, then advances p.

• Inside the loop's body, p now refers to the NEXT byte, not the one while (*p++) tested.

Net effect:

• First byte is never hashed.
• The NUL terminator \0 is hashed on the last iteration.
• The loop does not read past the terminator in the body, but it does incorporate \0 into the hash, which is almost certainly unintended, and this happens for all inputs.

example code

[VbhvGupta]

while (*p++)
hash = (hash << 5) - (hash + *p);

Also, the calculation of hash seems inconsistent.

hash = (hash << 5) - (hash + *p);
evaluates to -
hash = hash * 32 - hash - *p which is -> hash = hash * 31 - *p

Is this intentional?

I think
hash = (hash << 5) - hash + *p; should be used.

[madewokherd]

The difference between subtracting or adding *p is not obvious to me here.

[madewokherd]

Made an MR: https://gitlab.winehq.org/mono/mono/-/merge_requests/146

[akoeplinger]

We have the same issue in

mono/mono/metadata/metadata.c

Lines 5879 to 5900 in 0f53e9e

	/*
	* mono_metadata_str_hash:
	*
	* This should be used instead of g_str_hash for computing hash codes visible
	* outside this module, since g_str_hash () is not guaranteed to be stable
	* (its not the same in eglib for example).
	*/
	guint
	mono_metadata_str_hash (gconstpointer v1)
	{
	/* Same as g_str_hash () in glib */
	/* note: signed/unsigned char matters - we feed UTF-8 to this function, so the high bit will give diferent results if we don't match. */
	unsigned char *p = (unsigned char *) v1;
	guint hash = *p;
	while (*p++) {
	if (*p)
	hash = (hash << 5) - hash + *p;
	}
	return hash;
	}

[akoeplinger]

@madewokherd @VbhvGupta let me know if you plan on upstreaming this to https://github.com/dotnet/runtime, otherwise I can do it next week.

[madewokherd]

I don't plan to upstream it, because I don't have a working build tree for dotnet runtime (and I forget there are any common parts left).

I will take a look at the function you pointed out, thanks.

[madewokherd]

I don't think g_metadata_str_hash has this issue. The hash is initialized to *p and updates to it are gated on *p being non-zero. It is a bit convoluted and could be simplified, but as long as it's working I don't really want to mess with it.

[akoeplinger]

but it would still skip the first byte?

[madewokherd]

The first byte is accounted for in initialization guint hash = *p;