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

           Summary: GC.malloc(sz, GC.BlkAttr.APPENDABLE) fails after a
                    certain size
           Product: D
           Version: unspecified
          Platform: All
        OS/Version: Linux
            Status: NEW
          Severity: major
          Priority: P2
         Component: druntime
        AssignedTo: nobody@puremagic.com
        ReportedBy: monarchdodra@gmail.com


--- Comment #0 from monarchdodra@gmail.com 2013-07-09 13:56:40 PDT ---
As the title explains, after a certain size (2048 for my 32 bit install on an 64 linux), the appendable data cannot be exploited anymore:

//--------
import std.stdio;
import core.memory;

void main()
{
    for ( size_t i = 4 ; i < 1_000_000 ; i *= 1.4 )
    {
        ubyte[] s;
        s.reserve(i);
        writefln("%6s: s.capacity  is %6s", i, s.capacity);
        assert(s.capacity >= i);
        auto p = s.ptr;
        auto s2 = p[0 .. 0];
        writefln("%6s: s2.capacity is %6s", i, s2.capacity);
        assert(s2.capacity >= i);
    }
    for ( size_t i = 4 ; i < 1_000_000 ; i *= 1.4 )
    {
        ubyte*  p = cast(ubyte*)GC.malloc(i, GC.BlkAttr.APPENDABLE);
        ubyte[] s = p[0 .. 0];
        writefln("%6s: s.capacity  is %6s", i, s.capacity);
        assert(s.capacity + 4 >= i); //This ends up failing.
    }
}
//--------
439521: s.capacity  is 442351
439521: s2.capacity is 442351
615329: s.capacity  is 618479
615329: s2.capacity is 618479
861460: s.capacity  is 864239
861460: s2.capacity is 864239
     4: p.capacity  is     15
     5: p.capacity  is     15
     6: p.capacity  is     15
     8: p.capacity  is     15
...
  1443: p.capacity  is   2046
  2020: p.capacity  is   2046
  2827: p.capacity  is      0
core.exception.AssertError@main(24): Assertion failure
//--------

I find this strange, because the first test shows that the allocation size should not be a barrier.

Is the APPENDABLE data miss-placed or something? I can't really make sense of why there would be a different behaviour between "s2" or "p" ... ?

This is problematic, as "malloc(APPENDABLE)" is the only way to allocate a "true" d slice manually. Without this, functions such as array or appender, will return arrays that will relocate after the very first append :(

-- 
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=10589


Rainer Schuetze <r.sagitario@gmx.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |r.sagitario@gmx.de


--- Comment #1 from Rainer Schuetze <r.sagitario@gmx.de> 2013-07-12 13:37:39 PDT ---
I think you are mixing two levels of abstractions here:

        ubyte*  p = cast(ubyte*)GC.malloc(i, GC.BlkAttr.APPENDABLE);
        ubyte[] s = p[0 .. 0];
        writefln("%6s: s.capacity  is %6s", i, s.capacity);

GC.malloc requests raw memory from the GC. capacity is a function very specific to the way arrays are implemented on top of it in rt/lifetime.d. It assumes that any allocation with bit APPENDABLE set and that is larger than a page of 4kB reserves 16 bytes at the start of the allocation to store the actually used length of the memory.

So, to create an empty array manually that works with capacity, you'd have to set s to

   auto start = i <= 2048 ? 0 : 16;
   ubyte[] s = p[start .. start];

and you'd better clean that full memory block first to avoid the length field containing garbage.

-- 
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=10589



--- Comment #2 from monarchdodra@gmail.com 2013-07-12 14:29:45 PDT ---
(In reply to comment #1)
> I think you are mixing two levels of abstractions here:
> 
>         ubyte*  p = cast(ubyte*)GC.malloc(i, GC.BlkAttr.APPENDABLE);
>         ubyte[] s = p[0 .. 0];
>         writefln("%6s: s.capacity  is %6s", i, s.capacity);
> 
> GC.malloc requests raw memory from the GC. capacity is a function very specific
> to the way arrays are implemented on top of it in rt/lifetime.d. It assumes
> that any allocation with bit APPENDABLE set and that is larger than a page of
> 4kB reserves 16 bytes at the start of the allocation to store the actually used
> length of the memory.
> So, to create an empty array manually that works with capacity, you'd have to
> set s to
> 
>    auto start = i <= 2048 ? 0 : 16;
>    ubyte[] s = p[start .. start];

Hum. That worked.

Is the memory layout for the APPENDABLE data documented somewhere, or are these just reverse-engineered magic numbers?

> and you'd better clean that full memory block first to avoid the length field containing garbage.

Nope (I think). Length is carried in the slice, not the block. Block only contains capacity/used info.

------------------------------------------------------------------------

Thank you for your answer.

I suppose the behavior isn't going to change. Still, this requires more support. I think APPENDABLE should be better documented.

In particular, the magic numbers should be user accessible via manifest constants, or functions, so as to not have to guess/reverse engineer them. This is what I've discovered:

   0 -  256 bytes:
       1 Byte APPENDABLE info at end;
         Capacity = memory size -  1;
 257 - 2048 bytes:
       2 Byte APPENDABLE info at end;
         Capacity = memory size -  2;
2049 - **** bytes:
      16 Byte APPENDABLE info at beginning;
       1 Byte unknown info at end;
         Capacity = memory size - 17;

Are these numbers platform depending? What the heck is that 1 byte that leads to 17 byte difference I'm seeing.

-- 
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=10589



--- Comment #3 from Rainer Schuetze <r.sagitario@gmx.de> 2013-07-12 14:59:12 PDT ---
>Is the memory layout for the APPENDABLE data documented somewhere, or are these
just reverse-engineered magic numbers?

There is some description in rt/lifetime.d starting around line 200.

>Nope (I think). Length is carried in the slice, not the block.
> Block only contains capacity/used info.

Sorry, I meant the "used" info that must be reset.

>In particular, the magic numbers should be user accessible via manifest
> constants, or functions, so as to not have to guess/reverse engineer them.

The constants are defined privately in lifetime.d as SMALLPAD, MEDPAD and LARGEPAD. I suspect the trailing byte for large arrays is added so that arr[$..$] always points into the same memory block, and not the next 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=10589


monarchdodra@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|druntime                    |websites
           Severity|major                       |enhancement


--- Comment #4 from monarchdodra@gmail.com 2013-07-14 03:18:00 PDT ---
(In reply to comment #3)
> >Is the memory layout for the APPENDABLE data documented somewhere, or are these
> just reverse-engineered magic numbers?
> 
> There is some description in rt/lifetime.d starting around line 200.
> 
> >Nope (I think). Length is carried in the slice, not the block.
> > Block only contains capacity/used info.
> 
> Sorry, I meant the "used" info that must be reset.
> 
> >In particular, the magic numbers should be user accessible via manifest
> > constants, or functions, so as to not have to guess/reverse engineer them.
> 
> The constants are defined privately in lifetime.d as SMALLPAD, MEDPAD and LARGEPAD. I suspect the trailing byte for large arrays is added so that arr[$..$] always points into the same memory block, and not the next one.

Ok. I have just some tiny questions left, if you'd care to instruct me:
1. Why does the "Place at beginning" scheme start at 2K bytes, when a page is
4K byte?
2. Why is the padding 16 bytes? You'd think 8 is enough...? Is there a reason,
or is it just "future proofing"?

I'll write up the info acquired and update the doc.

-- 
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=10589



--- Comment #5 from Rainer Schuetze <r.sagitario@gmx.de> 2013-07-14 03:32:13 PDT ---
(In reply to comment #4)

> Ok. I have just some tiny questions left, if you'd care to instruct me:
> 1. Why does the "Place at beginning" scheme start at 2K bytes, when a page is
> 4K byte?

Allocation sizes below 4k are rounded up to the next power of 2, so if the allocation is larger than 2048, a full page is used by the GC. The array functions then assume that extending is possible and place information at the start of the buffer. All this is very specific to the currnt GC implementation.

> 2. Why is the padding 16 bytes? You'd think 8 is enough...? Is there a reason, or is it just "future proofing"?

It is necessary to support alignment attributes in arrays of structs (at least up to 16) or alignment for SIMD vectors.

> 
> I'll write up the info acquired and update the doc.

Thanks.

-- 
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=10589


monarchdodra@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


--- Comment #6 from monarchdodra@gmail.com 2013-07-14 09:41:03 PDT ---
(In reply to comment #5)
> (In reply to comment #4)
> > Ok. I have just some tiny questions left, if you'd care to instruct me:
> > 1. Why does the "Place at beginning" scheme start at 2K bytes, when a page is
> > 4K byte?
> 
> It is necessary to support alignment attributes in arrays of structs (at least up to 16) or alignment for SIMD vectors.

That makes sense I guess. By keeping it to a default 16, it avoids the overhead and complexity of calculating alignement.

> > 2. Why is the padding 16 bytes? You'd think 8 is enough...? Is there a reason, or is it just "future proofing"?
> 
> Allocation sizes below 4k are rounded up to the next power of 2, so if the allocation is larger than 2048, a full page is used by the GC. The array functions then assume that extending is possible and place information at the start of the buffer.

Derp.

> All this is very specific to the currnt GC implementation.

This. Because it is so specific, I have the feeling that all that has been said here is useless at the end of the day. Only writters of druntime, or users who are writting their own GC, could make use of this. The end user, even a library writer, can't make use of this information.

> > I'll write up the info acquired and update the doc.
> 
> Thanks.

I think I'll just end up writing that the only thing it does (technically) is set the bit "APPENDABLE" to the memory block. That its exploitation is ultimately implementation dependent.

--------

I was able to work around my issue though: By using reserve + assumeSafeAppend, I can get what it was that I wanted to work:

Check this out:
ushort[] a;
a.reserve(20); //GC appendable allocation.
a = a.ptr[0 .. 20]; //occupy space
assumeSafeAppend(a); //Take ownership of used space
assert(a.capcity >= 20);

Pretty neat huh?

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