From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Natasha Kerensikova Newsgroups: comp.lang.ada Subject: Re: Can anyone help with GNAT.Perfect_Hash_Generators ? (Possible memory corruption) Date: Tue, 6 Sep 2016 19:24:55 -0000 (UTC) Organization: A noiseless patient Spider Message-ID: References: <397dd8cb-2afc-43cd-972d-3b1a5a90cd5d@googlegroups.com> Injection-Date: Tue, 6 Sep 2016 19:24:55 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="eab84d932a0f4c9d4606240766f0f5e7"; logging-data="5255"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/vKG/On5JG8cAzAKcVkf+y" User-Agent: slrn/1.0.2 (FreeBSD) Cancel-Lock: sha1:xoEINsAslrAXJHKm6HJxFUTot+w= Xref: news.eternal-september.org comp.lang.ada:31710 Date: 2016-09-06T19:24:55+00:00 List-Id: Hello, On 2016-09-05, Stephen Leake 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