Re: Can anyone help with GNAT.Perfect_Hash_Generators ? (Possible memory corruption)

[Natasha Kerensikova <lithiumcat@instinctive.eu>]

Hello,

On 2016-09-05, Stephen Leake <stephen_leake@stephe-leake.org> wrote:
> Please post the code that shows the problem; it's very hard to say
> anything useful otherwise. If the code is large, please try to reduce
> it to a minimal set that shows the problem.

It took me that long to make the minimal reproducer. Maybe it's obvious
only to me because of my heavy C background, but memory corruption that
depends on seemingly unrelated can take weeks to reproduce reliably.

I thought I would post anyway, in hope of anyone sharing general hints
for that kind of problem, that might be worth trying even without
further detail on my particular instance of the problem.

>> Now one of the reasons I like Ada so much is that under normal
>> circumstances it's impossible to corrupt memory, especially in a way
>> that depends on what other code is compiled besides it. 
>
> Yes; you should get an exception or compilation error before
> corrupting memory.
>
> However, some of the GNAT packages are implemented in C, so they don't
> have that level of protection. But AdaCore is very careful in
> implementing those packages, and guarantees them for paying customers,
> so you should expect them to work.

The problem is in a package that seems written in Ada.

>> So is there anybody who can help with it? Or give me any clue?
>> Should I offer the verbose log, the source code, some other info?
>
> the log and the source code would be helpful.

OK so now for the reproducer and the current details on my particular
problem. Everything relevant is available at
http://users.instinctive.eu/nat/phg/

All the Ada files are library-level procedures, without any dependency
except Ada.Characters.Latin_1 and GNAT.Perfect_Hash_Generators. I
compiled them with FSF GNAT 4.9.3, 5.4.0 and 6.2.0, each with -O0 and
-O3, under FreeBSD 10.3-RELEASE on a 64-bit intel platform. The result
was exactly the same in all these conditions.

For each phg?.adb, the corresponding phg?.txt is the output of the
compiled binary, which contains only traces from
GNAT.Perfect_Hash_Generators.

phg1.adb is my first attempt at a minimal reproducer, this is exactly
the sequence of calls when the problem happens. But this minimal code
works perfectly, so it's not very useful except as a control.

After a long series of simple code that works and big code that doesn't,
I managed to isolate the trigger: it came from my having the keys not as
a set of separate strings, but a substrings of a concatenated big string
(that's how it is stored in my big code). That's in phg2.adb, the big
string and the offsets of the slices inside it. At least on my machines,
it reliably reproduce the memory corruption issue.

As I mentioned in the previous post, when comparing phg1.txt and
phg2.txt one can see that the sequence of inserted keys are identical,
and then the Initial Key Tables are identical too. But immediately after
the initial key table dump, one can see the 35 vs 36 different classes
of first-character. It's easy to compute programmatically than to see
with the eyes, but there are really only 35 different leading
characters. Then much later, one can find the Reduced Keys Table for
positions (1, 2, 3, 4), where item #67 is "http" when it works and a
bunch NUL when it doesn't.

Following the realization that the big-superstring was the trigger, I
suspected that the corruption came from the fact that all keys came from
a single object. So I tried with one object per key, created from the
big superstring, before feeding them to GNAT.Perfect_Hash_Generators.
That's phg3.adb, and indeed, it does work (phg3.txt is exactly identical
to phg1.txt)

But then I realized (and made more obvious in phg3.adb source) that not
only was I creating a new object for each key, but I was also changing
the index values. So I made phg4.adb, with independent objects having
the same indices as the substrings. And it also triggers the problem
(phg4.txt is exactly identical to phg4.txt).

So at this my conclusion is that GNAT.Perfect_Hash_Generators somehow
works fine with 1-based string, but has trouble dealing with strings
with larger indices. The "http://" that gets corrupted is the slice
Values (130 .. 136). It is larger than my usual indices, but that's
still very small for a (32-bit on my platform) Positive.

And with this, I have reached the limit of my investigative powers.
The only other potentially useful thing I found is in the source code of
GNAT.Perfect_Hash_Generators (g-pehage.adb), the argument to the Insert
procedure is copied in the internal state using `new String'(S)` but I
have no idea what it does to indices or why it would change anything
later on.

At least now I have a reproducer and a workaround, but I would still be
very interested in understanding how such a silent corruption can happen
in pure Ada code. If only to ensure I never craft myself into a similar
situation.


Hoping some can help,
Natasha