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

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

[Natasha Kerensikova]

Hello,

I'm afraid this is a bit off-topic, since I'm asking about a package
provided with GNAT rather than Ada language, I'm very lost and would
greatly appreciate any hint or help to work around it.

So I'm using GNAT.Perfect_Hash_Generators in two different programs, but
with the same sequence of calls : 254 times Insert, then Initialize and
Compute. The problem already shows at this point, even though I loop
around retrying with different seeds and/or more vertices.

In one of the program, everything works fine. In the second program, it
doesn't seem to terminate. But turning on the verbose mode, it appears
that one of the keys gets corrupted.

Looking at the verbose log generated by GNAT.Perfect_Hash_Generators,
the sequence of "Inserting" is identical, then the "Initial Key Table"
looks fine, then there is the first line that differs in both runs,
"Selecting position 1 results in 35 differences", when it works, while
it finds 36 differences when it doesn't. And I can confirm that there are
only 35 different leading characters in this set of keys.

Then are sets of keys that I really can't interpret, but they are
slightly different.

And then there is the "Reduced Keys Table", after having selected the
position set (1, 2, 3, 4). So if I guess correctly, the reduced key
table is supposed to have the first four characters of the correspond
keys. And that is indeed the case, except for key #67, which is dumped
as seven NUL characters, when the original key was "http://" and when it
works it is reduced to "http".

So at this point, my guess is that somehow something corrupts the key
table, and my key #67 gets turned into a lot of NUL characters, and
that's how it counts 36 different leading characters.

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. So I'm pretty
much at loss when trying to debug it, especially in code I haven't
written using a complex algorithm on which I have no clue.

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?

Or should I just consider myself lucky when a GNAT.* package works, and
find some other solution when they don't?


Thanks in advance for your help,
Natasha

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

[Stephen Leake]

On Sunday, September 4, 2016 at 2:22:02 PM UTC-5, Natasha Kerensikova wrote:
> Hello,
> 
> I'm afraid this is a bit off-topic, since I'm asking about a package
> provided with GNAT rather than Ada language, 

No problem; that's on topic for this group.

> I'm very lost and would
> greatly appreciate any hint or help to work around it.
> 
> So I'm using GNAT.Perfect_Hash_Generators in two different programs, but
> with the same sequence of calls : 254 times Insert, then Initialize and
> Compute. The problem already shows at this point, even though I loop
> around retrying with different seeds and/or more vertices.

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.

Also state what version of the compiler, on what OS.

> 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.

> 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.

> Or should I just consider myself lucky when a GNAT.* package works, and
> find some other solution when they don't?

No, they all should "just work", but sometimes they have bugs, which should be reported.

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

[Natasha Kerensikova]

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

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

[Florian Weimer]

* Natasha Kerensikova:

> 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.

Yes, that's reasonable to assume.  It's a relatively common source of
bugs in Ada library code.

One way to pin-point this further is to makea copy of the
g-pehage.ads, g-pehage.adb files, rename the package, and compile it
as part of your project, so that the usual Ada checks aren't
eliminated.

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

[Jeffrey R. Carter]

On 09/06/2016 12:52 PM, Florian Weimer wrote:
> 
> One way to pin-point this further is to makea copy of the
> g-pehage.ads, g-pehage.adb files, rename the package, and compile it
> as part of your project, so that the usual Ada checks aren't
> eliminated.

This gives

$ ./phg2 >phg2.txt

raised CONSTRAINT_ERROR : perfect_hash_generators.adb:2268 index check failed

So this appears to be an error in GNAT.Perfect_Hash_Generators compounded by it
having been compiled with checks turned off.

-- 
Jeff Carter
"I'm off to Alaska. If you need me, I'll be at
Frozen Tundra 6-9290."
Play It Again, Sam
130

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

[Simon Wright]

Florian Weimer <fw@deneb.enyo.de> writes:

> * Natasha Kerensikova:

(BTW, phg4 failed badly with "too many tries" or some such)

>> 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.
>
> Yes, that's reasonable to assume.  It's a relatively common source of
> bugs in Ada library code.
>
> One way to pin-point this further is to makea copy of the
> g-pehage.ads, g-pehage.adb files, rename the package, and compile it
> as part of your project, so that the usual Ada checks aren't
> eliminated.

Yes. With phg2, under gdb, macOS, GNAT GPL 2016,

Catchpoint 1, CONSTRAINT_ERROR (perfect_hash_generators.adb:2268 index check failed) at 0x000000010000e03e in perfect_hash_generators.select_char_position.count_different_keys (
    table=..., last=1, pos=1) at perfect_hash_generators.adb:2268
2268	               C := WT.Table (Reduced (K))(Pos);
(gdb) l
2263	
2264	            --  Count the occurrences of the different characters
2265	
2266	            N := (others => 0);
2267	            for K in Table (S).First .. Table (S).Last loop
2268	               C := WT.Table (Reduced (K))(Pos);
2269	               N (C) := N (C) + 1;
2270	            end loop;
2271	
2272	            --  Update the number of different keys. Each character used
(gdb) bt
#0  <__gnat_debug_raise_exception> (e=0x100059440, message=...) at s-excdeb.adb:43
#1  0x0000000100019e8c in ada.exceptions.complete_occurrence (x=0x100500af0)
    at a-except.adb:925
#2  0x0000000100019e9b in ada.exceptions.complete_and_propagate_occurrence (
    x=0x100500af0) at a-except.adb:936
#3  0x000000010001a2a6 in ada.exceptions.raise_with_location_and_msg (e=0x100059440, 
    f=(system.address) 0x10003ca64, l=2268, c=0, m=(system.address) 0x10003e640)
    at a-except.adb:1162
#4  0x0000000100019e61 in <__gnat_raise_constraint_error_msg> (file=<optimized out>, 
    line=<optimized out>, column=<optimized out>, msg=<optimized out>)
    at a-except.adb:891
#5  0x000000010001a390 in <__gnat_rcheck_CE_Index_Check> (file=<optimized out>, 
    line=<optimized out>) at a-except.adb:1237
#6  0x000000010000e03e in perfect_hash_generators.select_char_position.count_different_keys (table=..., last=1, pos=1) at perfect_hash_generators.adb:2268
#7  0x000000010000ca72 in perfect_hash_generators.select_char_position ()
    at perfect_hash_generators.adb:2326
#8  0x000000010000354b in perfect_hash_generators.compute (position=...)
    at perfect_hash_generators.adb:685
#9  0x000000010000f466 in phg2 () at phg2.adb:52
(gdb) p k
$1 = 67
(gdb) p pos
$2 = 1
(gdb) p reduced(k)
$3 = 322
(gdb) p table(s)
$4 = (first => 0, last => 253)

... gdb doesn't know what WT.Table is ... it's in an instantiation of
gnat.table ..


You were right about the strings, this

with Ada.Text_IO;
procedure Str is
   type A is access String;
   S : String := "xxxhelloyyy";
   P : A;
begin
   P := new String'(S (4 .. 8));
   Ada.Text_IO.Put_Line
     ("""" & P.all & """ has indices"
        & P.all'First'Img & " .." & P.all'Last'Img);
end Str;

gives

$ ./str
"hello" has indices 4 .. 8

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

[Anh Vo]

On Tuesday, September 6, 2016 at 2:04:43 PM UTC-7, Simon Wright wrote:
> Florian Weimer <fw@deneb.enyo.de> writes:
> 
> > * Natasha Kerensikova:
> 
> (BTW, phg4 failed badly with "too many tries" or some such)
> 
> >> 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.
> >
> > Yes, that's reasonable to assume.  It's a relatively common source of
> > bugs in Ada library code.
> >
> > One way to pin-point this further is to makea copy of the
> > g-pehage.ads, g-pehage.adb files, rename the package, and compile it
> > as part of your project, so that the usual Ada checks aren't
> > eliminated.
> 
> Yes. With phg2, under gdb, macOS, GNAT GPL 2016,
> 
> Catchpoint 1, CONSTRAINT_ERROR (perfect_hash_generators.adb:2268 index check failed) at 0x000000010000e03e in perfect_hash_generators.select_char_position.count_different_keys (
>     table=..., last=1, pos=1) at perfect_hash_generators.adb:2268
> 2268	               C := WT.Table (Reduced (K))(Pos);
> (gdb) l
> 2263	
> 2264	            --  Count the occurrences of the different characters
> 2265	
> 2266	            N := (others => 0);
> 2267	            for K in Table (S).First .. Table (S).Last loop
> 2268	               C := WT.Table (Reduced (K))(Pos);
> 2269	               N (C) := N (C) + 1;
> 2270	            end loop;
> 2271	
> 2272	            --  Update the number of different keys. Each character used
> (gdb) bt
> #0  <__gnat_debug_raise_exception> (e=0x100059440, message=...) at s-excdeb.adb:43
> #1  0x0000000100019e8c in ada.exceptions.complete_occurrence (x=0x100500af0)
>     at a-except.adb:925
> #2  0x0000000100019e9b in ada.exceptions.complete_and_propagate_occurrence (
>     x=0x100500af0) at a-except.adb:936
> #3  0x000000010001a2a6 in ada.exceptions.raise_with_location_and_msg (e=0x100059440, 
>     f=(system.address) 0x10003ca64, l=2268, c=0, m=(system.address) 0x10003e640)
>     at a-except.adb:1162
> #4  0x0000000100019e61 in <__gnat_raise_constraint_error_msg> (file=<optimized out>, 
>     line=<optimized out>, column=<optimized out>, msg=<optimized out>)
>     at a-except.adb:891
> #5  0x000000010001a390 in <__gnat_rcheck_CE_Index_Check> (file=<optimized out>, 
>     line=<optimized out>) at a-except.adb:1237
> #6  0x000000010000e03e in perfect_hash_generators.select_char_position.count_different_keys (table=..., last=1, pos=1) at perfect_hash_generators.adb:2268
> #7  0x000000010000ca72 in perfect_hash_generators.select_char_position ()
>     at perfect_hash_generators.adb:2326
> #8  0x000000010000354b in perfect_hash_generators.compute (position=...)
>     at perfect_hash_generators.adb:685
> #9  0x000000010000f466 in phg2 () at phg2.adb:52
> (gdb) p k
> $1 = 67
> (gdb) p pos
> $2 = 1
> (gdb) p reduced(k)
> $3 = 322
> (gdb) p table(s)
> $4 = (first => 0, last => 253)
> 
> ... gdb doesn't know what WT.Table is ... it's in an instantiation of
> gnat.table ..
> 
> 
> You were right about the strings, this
> 
> with Ada.Text_IO;
> procedure Str is
>    type A is access String;
>    S : String := "xxxhelloyyy";
>    P : A;
> begin
>    P := new String'(S (4 .. 8));
>    Ada.Text_IO.Put_Line
>      ("""" & P.all & """ has indices"
>         & P.all'First'Img & " .." & P.all'Last'Img);
> end Str;
> 
> gives
> 
> $ ./str
> "hello" has indices 4 .. 8

Then, what would be the proper fix?

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

[Simon Wright]

Anh Vo <anhvofrcaus@gmail.com> writes:

> Then, what would be the proper fix?

To what? If you mean the apparent bug in GNAT.Perfect_Hash_Generators
then I have to say that's one of the more opaque pieces of Ada that I've
seen, not helped by being implemented over another piece of complex
software (GNAT.Table). Of course, it's implementing a complex algorithm.

I suppose it was written before Ada.Containers.

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

[Anh Vo]

On Thursday, September 8, 2016 at 10:04:06 AM UTC-7, Simon Wright wrote:
> Anh Vo <anhvofrcaus@gmail.com> writes:
> 
> > Then, what would be the proper fix?
> 
> To what? If you mean the apparent bug in GNAT.Perfect_Hash_Generators

Yes.

> then I have to say that's one of the more opaque pieces of Ada that I've
> seen, not helped by being implemented over another piece of complex
> software (GNAT.Table). Of course, it's implementing a complex algorithm.
> 
> I suppose it was written before Ada.Containers.

Of course, it is better alternative if Ada.Containers* have what  GNAT.Perfect_Hash_Generators has.

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

[Simon Wright]

Anh Vo <anhvofrcaus@gmail.com> writes:

> On Thursday, September 8, 2016 at 10:04:06 AM UTC-7, Simon Wright wrote:

>> then I have to say that's one of the more opaque pieces of Ada that I've
>> seen, not helped by being implemented over another piece of complex
>> software (GNAT.Table). Of course, it's implementing a complex algorithm.
>> 
>> I suppose it was written before Ada.Containers.
>
> Of course, it is better alternative if Ada.Containers* have what
> GNAT.Perfect_Hash_Generators has.

Pretty sure they don't.

But what I meant was, using Containers looks a lot simpler than using
Table.

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

[Jeffrey R. Carter]

On 09/08/2016 11:03 AM, Anh Vo wrote:
> On Thursday, September 8, 2016 at 10:04:06 AM UTC-7, Simon Wright wrote:
>> Anh Vo <anhvofrcaus@gmail.com> writes:
>>
>>> Then, what would be the proper fix?
>>
>> To what? If you mean the apparent bug in GNAT.Perfect_Hash_Generators
> 
> Yes.

Clearly it needs to have the assumption, that all Strings have a lower bound of
1, eliminated.

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail
15

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

[Natasha Kerensikova]

Hello,

On 2016-09-08, Jeffrey R. Carter <spam.jrcarter.not@spam.not.acm.org> wrote:
> On 09/08/2016 11:03 AM, Anh Vo wrote:
>> On Thursday, September 8, 2016 at 10:04:06 AM UTC-7, Simon Wright wrote:
>>> Anh Vo <anhvofrcaus@gmail.com> writes:
>>>
>>>> Then, what would be the proper fix?
>>>
>>> To what? If you mean the apparent bug in GNAT.Perfect_Hash_Generators
>> 
>> Yes.
>
> Clearly it needs to have the assumption, that all Strings have a lower bound of
> 1, eliminated.
>

I thought it would be easier to make the assumption internally true
instead.

Since the first thing it does with the input is to copy it internally
using the function New_Word, I would propose a fix along the line of
replacing it from

   function New_Word (S : String) return Word_Type is
   begin
      return new String'(S);
   end New_Word;

to

   function New_Word (S : String) return Word_Type is
      Result : Word_Type := new String (1 .. S'Length);
   begin
      Result.all := S;
      return Result;
   end New_Word;


That way there is no need to gather a deep understanding of the
algorithm to hunt all the places that rely on 'First = 1.
And I don't see any loss of performance or readability with this change,
in case anyone is worried about it.

However I haven't found the time yet to seriously test such a fix.


Natasha

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

[Jeffrey R. Carter]

On 09/08/2016 11:04 PM, Natasha Kerensikova wrote:
> 
> On 2016-09-08, Jeffrey R. Carter <spam.jrcarter.not@spam.not.acm.org> wrote:
>>
>> Clearly it needs to have the assumption, that all Strings have a lower bound of
>> 1, eliminated.
>>
> 
> I thought it would be easier to make the assumption internally true
> instead.
> 
> Since the first thing it does with the input is to copy it internally
> using the function New_Word, I would propose a fix along the line of
> replacing it from
> 
>    function New_Word (S : String) return Word_Type is
>    begin
>       return new String'(S);
>    end New_Word;
> 
> to
> 
>    function New_Word (S : String) return Word_Type is
>       Result : Word_Type := new String (1 .. S'Length);
>    begin
>       Result.all := S;
>       return Result;
>    end New_Word;

Perhaps I should have said, "all Strings passed to it have a lower bound of 1".
Clearly it can ensure any characteristic it likes about Strings it creates. The
current approach assumes S has a lower bound of 1; your proposal does not. So I
consider your proposal as doing what I said.

Does

   return new String (1 .. S'Length)'(S);

work?

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail
15

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

[J-P. Rosen]

Le 09/09/2016 à 08:04, Natasha Kerensikova a écrit :
> Since the first thing it does with the input is to copy it internally
> using the function New_Word, I would propose a fix along the line of
> replacing it from
> 
>    function New_Word (S : String) return Word_Type is
>    begin
>       return new String'(S);
>    end New_Word;
> 
> to
> 
>    function New_Word (S : String) return Word_Type is
>       Result : Word_Type := new String (1 .. S'Length);
>    begin
>       Result.all := S;
>       return Result;
>    end New_Word;
> 
Or even (avoids one copy):
   function New_Word (S : String) return Word_Type is
      subtype Slide is String (1 .. S'Length);
   begin
      return new String'(Slide(S));
   end New_Word;

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

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

[Florian Weimer]

* Florian Weimer:

> * Natasha Kerensikova:
>
>> 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.
>
> Yes, that's reasonable to assume.  It's a relatively common source of
> bugs in Ada library code.

I have filed <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77535>
and am testing a patch.

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

[Florian Weimer]

* Stephen Leake:

> However, some of the GNAT packages are implemented in C, so they don't
> have that level of protection.

I think the Ada parts are still compiled with -gnatpg, and:

  --  Overflow checks are on by default (Suppress set False) except in
  --  GNAT_Mode, where we want them off by default (we are not ready to
  --  enable overflow checks in the compiler yet, for one thing the case
  --  of 64-bit checks needs System.Arith_64 which is not a compiler
  --  unit and it is a pain to try to include it in the compiler.
  
  Suppress_Options.Suppress (Overflow_Check) := GNAT_Mode;