A simple question about the "new" allocator

A simple question about the "new" allocator

[NiGHTS]

With all default configurations using a typical Ada compiler, will the following code run indefinitely without fail or will it eventually crash?

procedure main is 

    Test : access Positive;

begin

    loop
        Test := new Positive;
    end loop;

end main;

If this does crash, what would be another way to write this program so that it does not crash? I would prefer not to use Ada.Unchecked_Deallocation.

Re: A simple question about the "new" allocator

[Dmitry A. Kazakov]

On Mon, 11 Aug 2014 23:54:50 -0700 (PDT), NiGHTS wrote:

> With all default configurations using a typical Ada compiler, will the following code run indefinitely without fail or will it eventually crash?
> 
> procedure main is 
> 
>     Test : access Positive;
> 
> begin
> 
>     loop
>         Test := new Positive;
>     end loop;
> 
> end main;
> 
> If this does crash, what would be another way to write this program so
> that it does not crash?
>
> I would prefer not to use Ada.Unchecked_Deallocation.

Write a custom memory pool that does not allocate anything. Make Test a
pointer to that pool.

P.S. It might sound silly, but such pools are actually useful. When the
object is already allocated and you want to initialize it and get a pointer
to, one way to do that is using a fake allocator.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: A simple question about the "new" allocator

[G.B.]

On 12.08.14 09:35, Dmitry A. Kazakov wrote:
> On Mon, 11 Aug 2014 23:54:50 -0700 (PDT), NiGHTS wrote:
>
>> With all default configurations using a typical Ada compiler, will the following code run indefinitely without fail or will it eventually crash?
>>
>> procedure main is
>>
>>      Test : access Positive;
>>
>> begin
>>
>>      loop
>>          Test := new Positive;
>>      end loop;
>>
>> end main;
>>
>> If this does crash, what would be another way to write this program so
>> that it does not crash?
>>
>> I would prefer not to use Ada.Unchecked_Deallocation.
>
> Write a custom memory pool that does not allocate anything. Make Test a
> pointer to that pool.
>
> P.S. It might sound silly, but such pools are actually useful. When the
> object is already allocated and you want to initialize it and get a pointer
> to, one way to do that is using a fake allocator.

One such storage pool, tailored to the problem, and therefore likely
not applicable to every problem:

with System.Storage_Pools;
with System.Storage_Elements;

generic
    type T is private;
package My_Switching_Pool is

    pragma Preelaborate (My_Switching_Pool);

    use System;

    type Alternating_Pool
      is new Storage_Pools.Root_Storage_Pool with private;
    --  Provides storage for exactly two items of formal type `T`.

    overriding
    procedure Allocate
      (Pool                     : in out Alternating_Pool;
       Storage_Address          :    out Address;
       Size_In_Storage_Elements : in     Storage_Elements.Storage_Count;
       Alignment                : in     Storage_Elements.Storage_Count);
    --  makes the other of the two items available for storage

    overriding
    procedure Deallocate
      (Pool                     : in out Alternating_Pool;
       Storage_Address          : in     Address;
       Size_In_Storage_Elements : in     Storage_Elements.Storage_Count;
       Alignment                : in     Storage_Elements.Storage_Count);

    overriding
    function Storage_Size
      (Pool : Alternating_Pool) return Storage_Elements.Storage_Count;

private
    type Names is (Fst, Snd);
    type Pair is array (Names) of T;

    type Alternating_Pool
      is new Storage_Pools.Root_Storage_Pool with
       record
          In_Use : Names := Snd;
       end record;

    The_Data : Pair;

end My_Switching_Pool;

package body My_Switching_Pool is

    overriding
    procedure Allocate
      (Pool                     : in out Alternating_Pool;
       Storage_Address          :    out Address;
       Size_In_Storage_Elements : in     Storage_Elements.Storage_Count;
       Alignment                : in     Storage_Elements.Storage_Count)
    is
    begin
       -- switch components of `The_Data`
       Pool.In_Use := (if Pool.In_Use = Fst
                       then Snd
                       else Fst);
       Storage_Address := The_Data (Pool.In_Use)'Address;
    end Allocate;

    overriding
    procedure Deallocate
      (Pool                     : in out Alternating_Pool;
       Storage_Address          : in     Address;
       Size_In_Storage_Elements : in     Storage_Elements.Storage_Count;
       Alignment                : in     Storage_Elements.Storage_Count)
    is
    begin
       null;
    end Deallocate;

    overriding
    function Storage_Size
      (Pool : Alternating_Pool)
       return Storage_Elements.Storage_Count
    is
       use type Storage_Elements.Storage_Count;
    begin
       return Pair'Size / Storage_Elements.Storage_Element'Size;
    end Storage_Size;

end My_Switching_Pool;

with My_Switching_Pool;
procedure Main is

    package Two_Numbers is new My_Switching_Pool (T => Positive);

    The_Pool : Two_Numbers.Alternating_Pool;

    type Positive_Ptr is access Positive
       with Storage_Pool => The_Pool;

    Test : Positive_Ptr;

begin

    loop
       Test := new Positive;
    end loop;

end Main;

Re: A simple question about the "new" allocator

[sbelmont700]

On Tuesday, August 12, 2014 2:54:50 AM UTC-4, NiGHTS wrote:
> With all default configurations using a typical Ada compiler, will the following code run indefinitely without fail or will it eventually crash?
> 

Note that you are (intentionally or otherwise) using an 'anonymous allocator' for which the rules are much different, however as written it would still eventually crash.  Apart from the simple advice of just not using an allocator to begin with, I would expect the following to not leak any memory:

procedure main is
begin 
  loop 
    declare
      Test : access Positive := new Positive;
    begin
      null;
    end;
  end loop; 
end main; 

But it seems hit or miss whether or not a given compiler does this in the advised manner (mine doesn't seem to).  On the other hand, this seems to work more consistently:

procedure main is
  type T (x : access Positive) is null record;
begin 
   loop 
     declare
       Test : T (x => new Positive);
     begin
       null;
     end;
    end loop; 
end main;

Of course, there is still no real advantage to any of this over just a regular object.

-sb

Re: A simple question about the "new" allocator

[Shark8]

On 12-Aug-14 04:29, sbelmont700@gmail.com wrote:
> procedure main is
> begin
>    loop
>      declare
>        Test : access Positive := new Positive;
>      begin
>        null;
>      end;
>    end loop;
> end main;

I /think/ you can do it with a type definition on the inner-block:

declare
   Type Inner_Access is not null access positive;
   Test : Inner_Access := new Positive;
begin
   null;
end;

The reason is that leaving the nested-block's scope should force the 
deallocation of all Inner_Access types if I'm remembering the RM correctly.

Re: A simple question about the "new" allocator

[Adam Beneschan]

On Tuesday, August 12, 2014 11:49:03 AM UTC-7, Shark8 wrote:
> 
> > procedure main is
> > begin
> >    loop
> >      declare
> >        Test : access Positive := new Positive;
> >      begin
> >        null;
> >      end;
> >    end loop;
> > end main;
> 
> I /think/ you can do it with a type definition on the inner-block:
> 
> declare
>    Type Inner_Access is not null access positive;
>    Test : Inner_Access := new Positive;
> begin
>    null;
> end;
> 
> The reason is that leaving the nested-block's scope should force the 
> deallocation of all Inner_Access types if I'm remembering the RM correctly.

No, I don't think that's correct.  When an access type is declared in a nested block, all objects allocated using that access type (and not already deallocated) are *finalized*, but deallocation isn't required.  I don't see anything in the RM that says the storage must be reclaimed.

                               -- Adam

Re: A simple question about the "new" allocator

[Niklas Holsti]

On 14-08-12 22:10 , Adam Beneschan wrote:
> On Tuesday, August 12, 2014 11:49:03 AM UTC-7, Shark8 wrote:
>>
>>> procedure main is
>>> begin
>>>    loop
>>>      declare
>>>        Test : access Positive := new Positive;
>>>      begin
>>>        null;
>>>      end;
>>>    end loop;
>>> end main;
>>
>> I /think/ you can do it with a type definition on the inner-block:
>>
>> declare
>>    Type Inner_Access is not null access positive;
>>    Test : Inner_Access := new Positive;
>> begin
>>    null;
>> end;
>>
>> The reason is that leaving the nested-block's scope should force the 
>> deallocation of all Inner_Access types if I'm remembering the RM correctly.
> 
> No, I don't think that's correct.  When an access type is declared
> in a nested block, all objects allocated using that access type (and
> not already deallocated) are *finalized*, but deallocation isn't
> required.  I don't see anything in the RM that says the storage
> must be reclaimed.

Perhaps there is at least a suggestion of this?

RM 7.6.1(11.1/3) and 7.6.1(11.2/3) say that "Each nonderived access type
T has an associated collection, which is the set of objects created by
allocators of T, or of types derived from T. [...] The collection of an
access type is an object implicitly declared at the following place:
[...] For a named access type, the first freezing point of the type."

RM 7.6.1(11/3) says that "The finalization of a master performs
finalization of objects created by declarations in the master [...]
After the finalization of a master is complete, the objects finalized as
part of its finalization cease to exist, ...".

It seems to me that if an access type is declared in a block, then
completion of the block should by these rules cause the collection of
that access type, being an "object implicitly declared" in the block, to
cease to exist. For ordinary objects explicitly declared in a block, I
certainly expect the object's storage to be reclaimed when the object
ceases to exist on block exit; why should this not apply also to a
collection object, even if its declaration is implicit?

I have not found an explicit requirement on reclaiming the storage of a
collection in the Ada 2012 RM. As I remember, the Ada 83 RM had some
more explicit text about this, and I remember testing that it worked
(the collection's storage was reclaimed) with DEC Ada on a VAX.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .

Re: A simple question about the "new" allocator

[Adam Beneschan]

On Tuesday, August 12, 2014 2:53:36 PM UTC-7, Niklas Holsti wrote:

> It seems to me that if an access type is declared in a block, then
> completion of the block should by these rules cause the collection of
> that access type, being an "object implicitly declared" in the block, to
> cease to exist. For ordinary objects explicitly declared in a block, I
> certainly expect the object's storage to be reclaimed when the object
> ceases to exist on block exit; why should this not apply also to a
> collection object, even if its declaration is implicit?

I see your point.  But unless I've missed something, it's not an RM requirement.

However, if Storage_Size is specified for an access type, I think that the program does have to allocate a pool just for that type, and the storage for the pool does get reclaimed when the block is left.  (13.11(18))  The difference is that when Storage_Size is specified, the expectation is that the program will allocate a contiguous block of memory of that size to be used for allocations for that access type, and that storage block can simply be reclaimed all at once.  If Storage_Size is not specified, there won't be any such contiguous block. 

> I have not found an explicit requirement on reclaiming the storage of a
> collection in the Ada 2012 RM. As I remember, the Ada 83 RM had some
> more explicit text about this, and I remember testing that it worked
> (the collection's storage was reclaimed) with DEC Ada on a VAX.

I can't find anything explicit like this in the Ada 83 RM, even if Storage_Size is specified.

                            -- Adam

Re: A simple question about the "new" allocator

[sbelmont700]

On Tuesday, August 12, 2014 6:34:14 PM UTC-4, Adam Beneschan wrote:
> 
> However, if Storage_Size is specified for an access type, I think that the program does have to allocate a pool just for that type, and the storage for the pool does get reclaimed when the block is left.  (13.11(18))  The difference is that when Storage_Size is specified, the expectation is that the program will allocate a contiguous block of memory of that size to be used for allocations for that access type, and that storage block can simply be reclaimed all at once.  If Storage_Size is not specified, there won't be any such contiguous block. 
> 


Since we are already lawyering up, is it not true that

procedure main is 
begin 
  loop 
    declare 
      Test : access Positive := new Positive; 
    begin 
      null; 
    end; 
  end loop; 
end main;

is (advised to be) equivalent to this:

procedure main is 
begin 
  loop 
    declare
      p : Some_Default_Pool;
      type T is access Positive;
      for T'Storage_Pool use p;
      Test : T := new Positive; 
    begin 
      null; 
    end; 
  end loop; 
end main;

based on 13.11~25.4/2 ("Otherwise, a default storage pool should be created at the point where the anonymous access type is elaborated") and then consequently reclaimed when p goes out of scope?

-sb

Re: A simple question about the "new" allocator

[Adam Beneschan]

On Tuesday, August 12, 2014 4:14:16 PM UTC-7, sbelm...@gmail.com wrote:
> On Tuesday, August 12, 2014 6:34:14 PM UTC-4, Adam Beneschan wrote:
> 
> > 
> 
> > However, if Storage_Size is specified for an access type, I think that the program does have to allocate a pool just for that type, and the storage for the pool does get reclaimed when the block is left.  (13.11(18))  The difference is that when Storage_Size is specified, the expectation is that the program will allocate a contiguous block of memory of that size to be used for allocations for that access type, and that storage block can simply be reclaimed all at once.  If Storage_Size is not specified, there won't be any such contiguous block. 
> 
> > 
> 
> 
> 
> 
> 
> Since we are already lawyering up, is it not true that
> 
> 
> 
> procedure main is 
> 
> begin 
> 
>   loop 
> 
>     declare 
> 
>       Test : access Positive := new Positive; 
> 
>     begin 
> 
>       null; 
> 
>     end; 
> 
>   end loop; 
> 
> end main;
> 
> 
> 
> is (advised to be) equivalent to this:
> 
> 
> 
> procedure main is 
> 
> begin 
> 
>   loop 
> 
>     declare
> 
>       p : Some_Default_Pool;
> 
>       type T is access Positive;
> 
>       for T'Storage_Pool use p;
> 
>       Test : T := new Positive; 
> 
>     begin 
> 
>       null; 
> 
>     end; 
> 
>   end loop; 
> 
> end main;
> 
> 
> 
> based on 13.11~25.4/2 ("Otherwise, a default storage pool should be created at the point where the anonymous access type is elaborated") and then consequently reclaimed when p goes out of scope?

There's nothing that says *any* storage pool has to have its memory reclaimed, ever.  Suppose you declare your own:

    declare
        type My_Storage_Pool (Size : Storage_Count) is new Root_Storage_Pool
            with record ... end record;
        ... override Allocate, Deallocate, Storage_Size, Initialize, Finalize
        Pool : My_Storage_Pool;
        type T is access Positive;
        for T'Storage_Pool use Pool;
    begin
        ...
    end;

So when Pool goes out of scope, you'd think the memory used by Pool will be reclaimed, right?

Not necessarily.  Nothing says Pool has to have the memory used for allocation as part of the object.  The Initialize routine could allocate a byte array on the normal heap.  If this byte array isn't deallocated by My_Storage_Pool's Finalize routine, then the storage won't be reclaimed.

This isn't really relevant to the real world, since hopefully nobody would write My_Storage_Pool like that.  The point, here, is that you and others seem to be trying to infer an RM requirement (or "Implementation Advice"-type strong suggestion) based on some passages here and there, but in this case you're basing it on an assumption that isn't true.  That is, you're assuming that a "storage pool" that's declared in a local scope will have its storage reclaimed when the scope is exited.  I'm trying to demonstrate that this assumption is false, and thus your logic rests on a false assumption.

None of this says that you shouldn't expect the storage to be reclaimed, and you're certainly within your rights to complain to your compiler vendor if it isn't.  But I just don't see an RM requirement.  To me, the situation is what it's always been, since Ada 83: a program that does its own allocation is responsible for deallocating things itself; and, with the exception of specifying Storage_Size, in which case the program is expected to reserve a block of memory, there's no magic trick to get Ada to deallocate things for you.  At least, there's no guaranteed, portable magic trick.

                              -- Adam

Re: A simple question about the "new" allocator

[Dmitry A. Kazakov]

On Tue, 12 Aug 2014 16:41:10 -0700 (PDT), Adam Beneschan wrote:

> Not necessarily.  Nothing says Pool has to have the memory used for
> allocation as part of the object.  The Initialize routine could allocate a
> byte array on the normal heap.  If this byte array isn't deallocated by
> My_Storage_Pool's Finalize routine, then the storage won't be reclaimed.
> 
> This isn't really relevant to the real world, since hopefully nobody would
> write My_Storage_Pool like that.

Why? "Proxy pools" are quite useful.

Consider an implementation of doubly-linked list. The pointer to an element
goes to the proxy pool. Upon allocation the pool gets memory from the heap.
It allocates more memory than needed to keep the element adding space for
the list's forward and backward links. The advantage of this approach is
that the element can be of any type used as-is, links are totally
invisible, no extra redirection needed, pointer to the element is plain
direct access type.

Simple components has such an implementation:

http://www.dmitry-kazakov.de/ada/components.htm#Generic_Doubly_Linked_Web

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: A simple question about the "new" allocator

[Adam Beneschan]

On Wednesday, August 13, 2014 12:36:43 AM UTC-7, Dmitry A. Kazakov wrote:

> > This isn't really relevant to the real world, since hopefully nobody would
> > write My_Storage_Pool like that.
> 
> Why? "Proxy pools" are quite useful.

Sorry, I meant specifically allocating a block of storage on the heap, reserving a large chunk of memory, *and* forgetting to deallocate it at the end.  I hope nobody would write My_Storage_Pool like that.  My fault, I didn't express myself clearly.

                                -- Adam
 

Re: A simple question about the "new" allocator

[Niklas Holsti]

On 14-08-13 01:34 , Adam Beneschan wrote:
> On Tuesday, August 12, 2014 2:53:36 PM UTC-7, Niklas Holsti wrote:
> 
>> It seems to me that if an access type is declared in a block, then
>> completion of the block should by these rules cause the collection of
>> that access type, being an "object implicitly declared" in the block, to
>> cease to exist. For ordinary objects explicitly declared in a block, I
>> certainly expect the object's storage to be reclaimed when the object
>> ceases to exist on block exit; why should this not apply also to a
>> collection object, even if its declaration is implicit?
> 
> I see your point.  But unless I've missed something, it's not an RM
> requirement.

I believe I agree.

(I don't really understand why the RM makes these statements about the
"collection" as an "object". I guess these statements connect to some
general RM statements about objects, but I don't know which statements
the latter are.)

> However, if Storage_Size is specified for an access type, I think
> that the program does have to allocate a pool just for that type,
> and the storage for the pool does get reclaimed when the block is
> left.  (13.11(18))

Oh yes, that's the trick. Which gives a better answer to the OP's
question, doesn't it?

>> I have not found an explicit requirement on reclaiming the storage of a
>> collection in the Ada 2012 RM. As I remember, the Ada 83 RM had some
>> more explicit text about this, and I remember testing that it worked
>> (the collection's storage was reclaimed) with DEC Ada on a VAX.

It may be that I had a Storage_Size spec in that test of DEC Ada, I
don't clearly remember.

> I can't find anything explicit like this in the Ada 83 RM, even if
> Storage_Size is specified.

There's a kind of "exception proves the rule" in 4.8 (sorry, I don't see
the paragraph number):

  "2. The pragma CONTROLLED informs the implementation that automatic
storage reclamation must not be performed for objects designated by
values of the access type, except upon leaving the innermost block
statement, subprogram body, or task body that encloses the access type
declaration, or after leaving the main program."

The part "except upon leaving ..." suggests that storage is (or at least
may be) reclaimed when the access type declaration goes out of scope.
But you are right, it is not a requirement, probably it is just the
traditional RM permission to collect garbage.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .

Re: A simple question about the "new" allocator

[Adam Beneschan]

On Monday, August 11, 2014 11:54:50 PM UTC-7, NiGHTS wrote:
> With all default configurations using a typical Ada compiler, will the following code run indefinitely without fail or will it eventually crash?
> 
> 
> 
> procedure main is 
>     Test : access Positive;
> begin
>     loop
>         Test := new Positive;
>     end loop; 
> end main;

> If this does crash, what would be another way to write this program so that it does not crash? I would prefer not to use Ada.Unchecked_Deallocation.

I vote for

    procedure main is
    begin
        loop
           null;
        end loop;
    end main;

which would have the same effect as your orignal code but without crashing.  Really, the question "what would be another way to write this program so that it does not crash" makes no sense at all; before answering it, we would need specifics about just *what* you want to do without crashing.

For example, if you want "test := new Positive" to automatically deallocate the previously allocated Positive, since it isn't referenced any more, there are various "smart pointer" packages out there that keep a reference count.

But the question as posted isn't answerable.

                                -- Adam

Re: A simple question about the "new" allocator

[Jeffrey Carter]

On 08/11/2014 11:54 PM, NiGHTS wrote:
> With all default configurations using a typical Ada compiler, will the
> following code run indefinitely without fail or will it eventually crash?

With a typical Ada compiler, your program will crash. Ada's definition allows 
garbage collection but doesn't require it. I'm not aware of any compiler that 
implements it.

> If this does crash, what would be another way to write this program so that
> it does not crash? I would prefer not to use Ada.Unchecked_Deallocation.

If it didn't crash, your program would run forever without any visible effect; 
it's quite easy to write such a program. Presuming that's not what you're 
asking, you can repeatedly allocate memory using a safe pointer without running 
out of memory:

with PragmARC.Safe_Pointers;

procedure Does_Not_Crash is
    package Positive_Pointers is new PragmARC.Safe_Pointers (Object => Positive);

    Test : Positive_Pointers.Safe_Pointer;
begin -- Does_Not_Crash
    loop
       Test := Positive_Pointers.Allocate;
    end loop;
end Does_Not_Crash;

-- 
Jeff Carter
"There's no messiah here. There's a mess all right, but no messiah."
Monty Python's Life of Brian
84

Re: A simple question about the "new" allocator

[Robert A Duff]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> With a typical Ada compiler, your program will crash. Ada's definition
> allows garbage collection but doesn't require it. I'm not aware of any
> compiler that implements it.

I have used the Boehm conservative GC with Ada.

- Bob

Re: A simple question about the "new" allocator

[NiGHTS]

Thank you all for your help with this problem. After spending some time thinking about this issue and with what you all of you have prescribed as ways to avoid crashing the program, I think my approach will be to use access only on aliased variables that were instantiated using other devices that do not require the use of "new" directly.

G.B.'s storage pool approach intrigues me and I will be sure to study this code to help me understand how I can apply storage pools to various complex situations which are sure to come up. Though today I think I found good ways of avoiding "new" in the context described in my first message.

When instantiating new memory in a define block, when does the compiler use the stack memory and when does it use the heap? I worry that trying to avoid "new" will cause the stack memory to be out of control.