http://d.puremagic.com/issues/show_bug.cgi?id=4681

           Summary: Strange access violation Mandelbug with AAs + Appender
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Severity: critical
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: dsimcha@yahoo.com


--- Comment #0 from David Simcha <dsimcha@yahoo.com> 2010-08-19 10:15:45 PDT ---
The following code produces an access violation approximately 1 in 10 times when run.  From observations that I haven't been able to reduce to a small test case, it appears that memory corruption is also involved.  This bug is so non-deterministic that I haven't the slightest clue how to debug it further. It appears related to the order in which the arrays are appended.  I tried changing this to some simple deterministic things and can't reproduce this bug w/o the random index selection.

import std.stdio, std.random, std.array;

void main() {
    Appender!(float[], float)[string] aa;

    string[] indices = ["aa", "bb", "cc", "dd", "ee", "ff", "gg", "hh", "ii"];
    foreach(i; 0..10_000) {
        float f = i;
        auto index = indices[uniform(0, indices.length)];

        if(index !in aa) {
            aa[index] = typeof(aa[index]).init;
        }
        aa[index].put(f);
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681


David Simcha <dsimcha@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P1
           Severity|critical                    |regression


--- Comment #1 from David Simcha <dsimcha@yahoo.com> 2010-08-19 10:51:27 PDT ---
Can't reproduce this in 200 attempts on 2.047, whereas in 200 attempts on 2.048 I get 32 access violations.  It's a regression, and a pretty severe one.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681


kennytm@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kennytm@gmail.com


--- Comment #2 from kennytm@gmail.com 2010-08-19 11:11:21 PDT ---
Reproduced on Mac OS X (v2.048) too. The backtrace indicates the error starts
at .put().

0   x                                 0x0000253b
D3std5array18__T8AppenderTAfTfZ8Appender12readCapacityMFZk + 63
1   x                                 0x000026a9
D3std5array18__T8AppenderTAfTfZ8Appender8capacityMFZk + 81
2   x                                 0x00006372
D3std5array18__T8AppenderTAfTfZ8Appender10__T3putTfZ3putMFfZv + 118
3   x                                 0x00002330 _Dmain + 424
4   x                                 0x000118d7
D2rt6dmain24mainUiPPaZi7runMainMFZv + 23
5   x                                 0x0001180e
D2rt6dmain24mainUiPPaZi7tryExecMFMDFZvZv + 42
6   x                                 0x0001191f
D2rt6dmain24mainUiPPaZi6runAllMFZv + 59
7   x                                 0x0001180e
D2rt6dmain24mainUiPPaZi7tryExecMFMDFZvZv + 42
8   x                                 0x0001179b main + 179
9   x                                 0x0000217d start + 53

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681



--- Comment #3 from kennytm@gmail.com 2010-08-19 11:29:49 PDT ---
A much shorter test case:

    import std.random, std.array;

    void main() {
        Appender!(int[])[3] aa;
        foreach(i; 0..10000)
            aa[uniform(0, aa.length)].put(i);
    }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681



--- Comment #4 from David Simcha <dsimcha@yahoo.com> 2010-08-19 11:35:11 PDT ---
It's definitely a bug in Appender, not a bug in the runtime or AAs.  Replacing 2.048 Appender with 2.047 Appender in array.d and recompiling Phobos and my code makes this bug go away.

All the cruft about associative arrays and stuff is just artifacts of how I initially discovered this bug and the test case I was reducing from.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681



--- Comment #5 from kennytm@gmail.com 2010-08-19 11:46:51 PDT ---
Deterministic test case (always crash on my machine):

----

import std.array,std.stdio;

void main() {
    Appender!(uint[])[3] aa;

    auto x = [

0,1,1,0,2,1,2,2,1,2,0,0,2,1,1,1,2,0,0,0,0,0,0,2,1,2,1,0,1,2,0,0,0,2,0,1,

1,0,1,0,2,2,0,0,1,2,0,1,1,1,1,2,0,0,2,1,1,2,2,0,0,2,1,0,1,0,2,0,0,0,0,2,

2,2,1,1,0,0,2,2,0,0,2,1,2,1,0,1,0,1,2,1,1,2,1,1,0,1,2,2,1,0,1,0,0,0,2,1,

1,1,0,2,0,2,0,1,2,0,2,0,1,0,0,0,0,1,1,0,2,2,0,2,1,0,0,0,0,1,1,0,0,1,1,0,

2,2,0,2,2,2,2,0,1,1,1,2,0,0,0,2,1,2,0,2,0,1,0,2,1,0,2,1,2,0,0,1,2,1,1,2,

2,2,1,2,2,1,1,0,1,2,0,1,0,2,0,0,1,0,0,0,2,1,1,0,1,0,1,1,2,2,0,2,0,1,0,1,

2,1,1,1,0,0,0,0,1,0,2,2,2,2,2,1,0,0,0,0,0,1,0,2,1,0,2,2,1,0,2,2,0,0,1,1,

1,1,1,2,0,0,2,2,2,0,2,2,0,1,0,1,1,2,0,0,2,2,1,0,0,1,0,1,2,1,1,1,1,2,2,0,

0,2,2,2,0,2,2,2,2,1,2,1,1,2,1,0,1,1,2,1,0,2,0,1,1,2,1,0,1,2,2,0,1,2,0,0,

0,0,2,1,2,2,2,2,0,2,0,1,2,2,2,2,2,2,1,2,1,1,0,1,0,2,1,2,2,2,1,2,1,0,1,0,

2,1,2,2,2,2,2,2,0,0,1,0,2,1,0,1,0,0,1,1,0,0,2,0,0,2,2,2,2,1,1,1,0,1,0,0,

1,1,0,2,2,1,0,0,2,1,0,2,1,1,2,2,0,2,0,1,2,1,0,2,0,0,0,0,1,2,2,1,2,1,1,2,

1,1,0,1,0,2,2,2,1,1,2,2,0,2,2,2,2,2,1,1,0,0,1,0,0,0,0,0,0,1,0,2,1,1,1,1,

1,2,1,1,2,2,0,0,1,0,1,2,1,0,2,1,0,0,1,2,2,0,1,1,2,2,0,0,0,2,2,1,1,0,0,0,

0,1,2,2,0,1,0,0,1,2,0,2,2,2,1,1,0,0,0,0,1,2,0,1,0,1,1,2,2,2,2,2,0,2,1,1,

1,2,1,2,1,0,2,1,0,1,1,0,2,0,1,1,0,0,1,0,1,0,1,0,2,0,0,0,2,0,0,0,1,1,2,2,

1,0,0,1,2,2,2,0,1,0,2,2,1,2,1,1,1,1,1,2,1,1,2,1,2,1,1,1,0,0,2,0,2,2,1,1,

1,0,1,2,1,2,1,2,1,2,2,0,0,2,0,1,1,2,1,2,0,2,1,1,1,2,2,1,0,2,1,0,0,2,0,1,

2,0,0,0,1,2,2,2,1,1,2,1,2,0,0,1,2,0,2,1,1,0,1,0,1,1,2,0,0,2,0,0,1,0,2,2,

0,0,2,1,1,0,0,1,1,0,1,2,2,1,0,2,2,0,2,2,2,2,2,2,0,1,0,1,2,1,0,0,0,2,0,1,

2,2,0,2,0,2,2,0,2,1,1,2,1,0,0,1,0,1,0,1,1,0,0,2,2,2,2,0,1,0,2,1,0,0,0,1,

2,2,0,1,1,1,0,1,1,0,0,0,2,1,0,1,0,0,1,0,2,2,2,1,1,1,2,0,1,1,1,0,1,0,2,2,

1,1,0,1,0,0,2,2,2,0,2,1,2,0,0,1,0,2,0,0,1,1,1,2,1,0,1,2,2,1,2,1,0,1,2,2,

1,0,2,1,2,0,0,2,0,1,1,0,2,1,0,1,0,0,1,0,0,0,2,2,2,1,0,0,1,2,2,1,1,2,2,1,

1,1,2,2,1,2,1,1,2,1,1,0,2,2,2,0,0,2,1,2,2,1,2,0,1,1,2,0,2,0,2,1,2,2,0,1,

2,2,1,0,1,2,0,2,0,2,2,1,2,2,0,2,2,1,0,0,2,2,1,2,0,0,1,1,0,2,0,1,0,2,0,1,

1,0,0,0,2,1,1,0,0,2,1,1,0,0,2,2,2,0,1,0,0,1,2,1,2,1,2,1,2,2,2,0,1,1,1,2,

1,0,1,1,1,2,1,2,2,2,0,1,2,0,1,0,0,0,0,1,1,2,1,1,2,2,1,2,2,1,1,1,1,1,2,2,

0,0,1,1,1,1,0,2,1,0,1,0,0,2,0,0,1,0,2,1,0,1,0,0,1,2,0,1,1,1,2,1,0,1,1,2,

0,1,2,1,1,2,1,0,0,0,2,0,0,0,0,2,1,2,1,1,0,0,1,0,0,0,1,0,2,0,0,1,1,2,2,1,

2,1,2,0,0,0,0,1,0,0,1,0,0,1,0,1,0,2,0,0,0,1,1,1,1,0,2,1,2,1,1,2,2,0,1,0,

2,1,0,0,1,2,2,2,2,0,2,2,2,2,1,1,2,1,0,1,2,2,1,1,0,0,0,0,1,0,2,0,2,2,0,1,

0,0,0,2,2,0,2,0,0,2,2,2,0,1,1,1,2,1,2,1,2,2,1,0,2,1,2,1,2,1,1,0,0,1,2,1,

0,1,2,2,0,2,2,2,1,0,0,0,1,1,0,1,0,1,1,0,0,1,0,0,0,2,2,1,2,1,1,1,0,1,0,2,

0,2,1,1,0,0,1,1,2,1,2,2,0,1,2,1,1,1,2,1,1,2,1,1,0,1,0,2,0,2,2,2,0,1,1,0,

0,0,1,2,2,1,2,0,0,0,2,1,1,0,0,2,0,2,1,0,1,2,2,1,0,1,1,0,1,1,2,2,1,0,2,0,

1,2,0,0,1,2,2,2,1,1,1,2,0,2,2,0,0,0,0,0,0,2,2,2,1,2,1,0,2,0,2,1,0,0,1,0,

0,0,1,1,0,0,2,2,2,0,0,2,0,1,0,2,2,0,1,1,1,1,0,2,0,0,0,1,1,1,1,1,2,2,0,2,

2,0,1,0,2,1,0,0,1,0,0,1,1,1,0,0,0,0,2,0,1,0,1,1,0,2,2,0,0,2,0,2,1,0,1,2,

0,2,1,1,2,0,1,0,0,0,2,0,0,1,0,0,0,2,0,0,2,2,1,2,0,0,1,2,1,2,2,1,1,0,2,1,

2,2,2,1,1,1,0,2,2,2,1,2,2,2,2,0,0,2,1,0,0,1,2,1,2,1,1,2,2,1,2,1,2,0,2,1,

1,2,1,0,0,2,2,2,0,0,0,2,2,2,1,0,1,2,1,1,2,1,2,0,0,1,0,0,0,1,2,1,1,0,1,1,
        0,1,1
    ];

    foreach(v; x)
        aa[v].put(0);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681



--- Comment #6 from David Simcha <dsimcha@yahoo.com> 2010-08-20 18:10:15 PDT ---
(In reply to comment #5)
> Deterministic test case (always crash on my machine):

Apparently this test case is deterministic only on your machine.  On my machine it doesn't reproduce this bug.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681



--- Comment #7 from David Simcha <dsimcha@yahoo.com> 2010-08-20 18:43:24 PDT ---
Comment from Shin Fujishiro the Phobos mailing list, reproduced here to make it more public and permanent:

Seems like a bug of Appender.writeCapacity().  It often writes 'cap' to
wrong address; the following assertion fails:
==========
diff --git phobos/std/array.d phobos/std/array.d
index 6b62733..e6d3a62 100644
--- phobos/std/array.d
+++ phobos/std/array.d
@@ -736,10 +736,12 @@ private:
         auto p = cast(ubyte*) (pArray.ptr + pArray.length);
         if (cap < ubyte.max)
         {
+            assert(p + 1 <= GC.addrOf(pArray.ptr) + GC.sizeOf(pArray.ptr));
             *p = cast(ubyte) cap;
         }
         else if (cap < ushort.max)
         {
+            assert(p + 3 <= GC.addrOf(pArray.ptr) + GC.sizeOf(pArray.ptr));
             *p++ = ubyte.max;
             *p++ = cast(ubyte) cap;
             *p++ = cast(ubyte) (cap >> 8);
==========


Shin

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #8 from Don <clugdbug@yahoo.com.au> 2010-08-24 01:30:01 PDT ---
Here's another test case for what I believe is the same thing. It's memory corruption rather than a segfault. This is a regression since 2.047.

import std.stdio;
import std.array;

void main()
{
    Appender!(double[]) b, c;
    string[] t;
    t ~= "qqqqq";
    t ~= "qqqqq";
    double zzz;
    b.put( 111.1 );

    for (;;) {
        c.put(double.nan);
        b.put( 0);

        double qqq = b.data()[0];
        writefln("%s", qqq);
        assert(qqq>0);
    }
}
--------
111.1
111.1
111.1
111.1
nan
core.exception.AssertError@test(46): Assertion failure

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4681


nfxjfg@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nfxjfg@gmail.com


--- Comment #9 from nfxjfg@gmail.com 2010-08-24 02:18:39 PDT ---
There's some wtfish code in Appender, that probably tries to emulate how the runtime allocates arrays. I don't understand why it doesn't simply use the functions exported by the runtime. Even if not, there's no justification to duplicate all the code in Phobos, instead of extending the runtime itself.

Or maybe the original author thought a simple function call on array reallocation is to slow?

Also I doubt using gc_realloc is a good idea: in some cases, gc_realloc frees memory by force (similar to gc_free), and thus is unsafe in SafeD's definition. (Although I'm not quite sure if that is the case here.)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------