Allocators design flaw

Allocators design flaw

[Victor Porton]

It is impossible to properly implement an allocator through a C function 
(such as raptor_alloc_memory() from Raptor C library) which allocates a 
struct and returns the pointer to the allocated struct.

It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero integral 
multiple of D'Alignment..."

(If it were "The Alignment parameter is equal to D'Alignment", then we would 
be able just to check (in Allocate procedure implementation) that

pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
-- where Dummy_Record is an arbitrary C-convention record
-- (as all C records have the same alignment reqs)

So Alignment parameter may be arbitrarily big and the C function alignment 
may not conform to it.

Let us think how to work around (in Ada 202x) of this design flaw.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 04:53, Victor Porton wrote:
> It is impossible to properly implement an allocator through a C function
> (such as raptor_alloc_memory() from Raptor C library) which allocates a
> struct and returns the pointer to the allocated struct.
> 
> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero integral
> multiple of D'Alignment..."
> 
> (If it were "The Alignment parameter is equal to D'Alignment", then we would
> be able just to check (in Allocate procedure implementation) that
> 
> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
> -- where Dummy_Record is an arbitrary C-convention record
> -- (as all C records have the same alignment reqs)
> 
> So Alignment parameter may be arbitrarily big and the C function alignment
> may not conform to it.

Usually allocators return addresses already rounded and there is nothing 
to worry about.

> Let us think how to work around (in Ada 202x) of this design flaw.

If any it is _alloc_memory() flaw, not Ada's.

Add max alignment + log max alignment - 1 to the desired size. Add log 
max alignment to the returned address and round to the required 
alignment. Place the offset to original address in front (log alignment 
length). Return the rounded address. When freed use the stored offset to 
get the original address.

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

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> It is impossible to properly implement an allocator through a C function 
> (such as raptor_alloc_memory() from Raptor C library) which allocates a 
> struct and returns the pointer to the allocated struct.
>
> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero integral 
> multiple of D'Alignment..."
>
> (If it were "The Alignment parameter is equal to D'Alignment", then we would 
> be able just to check (in Allocate procedure implementation) that
>
> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
> -- where Dummy_Record is an arbitrary C-convention record
> -- (as all C records have the same alignment reqs)

See the arguments in the AI:
http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0193-1.txt?rev=1.8&raw=N

> So Alignment parameter may be arbitrarily big and the C function alignment 
> may not conform to it.

No bigger than 'Max_Alignment_For_Allocation.

> Let us think how to work around (in Ada 202x) of this design flaw.

If the C struct needs alignment greater than that of the elements of
which it is composed (see the AI for example) it would have it.

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 04:53, Victor Porton wrote:
>> It is impossible to properly implement an allocator through a C function
>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>> struct and returns the pointer to the allocated struct.
>> 
>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>> integral multiple of D'Alignment..."
>> 
>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>> would be able just to check (in Allocate procedure implementation) that
>> 
>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>> -- where Dummy_Record is an arbitrary C-convention record
>> -- (as all C records have the same alignment reqs)
>> 
>> So Alignment parameter may be arbitrarily big and the C function
>> alignment may not conform to it.
> 
> Usually allocators return addresses already rounded and there is nothing
> to worry about.
> 
>> Let us think how to work around (in Ada 202x) of this design flaw.
> 
> If any it is _alloc_memory() flaw, not Ada's.
> 
> Add max alignment + log max alignment - 1 to the desired size. Add log
> max alignment to the returned address and round to the required
> alignment. Place the offset to original address in front (log alignment
> length). Return the rounded address. When freed use the stored offset to
> get the original address.

Is "log" logarithm? Why do we need a logarithm?

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>> It is impossible to properly implement an allocator through a C function
>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>> struct and returns the pointer to the allocated struct.
>>
>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>> integral multiple of D'Alignment..."
>>
>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>> would be able just to check (in Allocate procedure implementation) that
>>
>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>> -- where Dummy_Record is an arbitrary C-convention record
>> -- (as all C records have the same alignment reqs)
> 
> See the arguments in the AI:
> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai05s/ai05-0193-1.txt?rev=1.8&raw=N
> 
>> So Alignment parameter may be arbitrarily big and the C function
>> alignment may not conform to it.
> 
> No bigger than 'Max_Alignment_For_Allocation.

This does not help.

>> Let us think how to work around (in Ada 202x) of this design flaw.
> 
> If the C struct needs alignment greater than that of the elements of
> which it is composed (see the AI for example) it would have it.

"it would have it"? What this sequence of English words mean?

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 04:53, Victor Porton wrote:
>> It is impossible to properly implement an allocator through a C function
>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>> struct and returns the pointer to the allocated struct.
>> 
>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>> integral multiple of D'Alignment..."
>> 
>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>> would be able just to check (in Allocate procedure implementation) that
>> 
>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>> -- where Dummy_Record is an arbitrary C-convention record
>> -- (as all C records have the same alignment reqs)
>> 
>> So Alignment parameter may be arbitrarily big and the C function
>> alignment may not conform to it.
> 
> Usually allocators return addresses already rounded and there is nothing
> to worry about.
> 
>> Let us think how to work around (in Ada 202x) of this design flaw.
> 
> If any it is _alloc_memory() flaw, not Ada's.
> 
> Add max alignment + log max alignment - 1 to the desired size. Add log
> max alignment to the returned address and round to the required
> alignment. Place the offset to original address in front (log alignment
> length). Return the rounded address. When freed use the stored offset to
> get the original address.

As far as I understand, it will not work, because the C library I am writing 
bindings for may try to free an object allocated by me (or I my need to free 
an object allocated by the library).

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Victor Porton wrote:

> It is impossible to properly implement an allocator through a C function
> (such as raptor_alloc_memory() from Raptor C library) which allocates a
> struct and returns the pointer to the allocated struct.
> 
> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
> integral multiple of D'Alignment..."
> 
> (If it were "The Alignment parameter is equal to D'Alignment", then we
> would be able just to check (in Allocate procedure implementation) that
> 
> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
> -- where Dummy_Record is an arbitrary C-convention record
> -- (as all C records have the same alignment reqs)
> 
> So Alignment parameter may be arbitrarily big and the C function alignment
> may not conform to it.
> 
> Let us think how to work around (in Ada 202x) of this design flaw.

The best solution I found for my concrete problem (allocate a C struct with 
the C library allocating function raptor_alloc_memory() rather then with the 
standard storage pool) is:

Let the (C compatible) type of the struct be T.

Using raptor_alloc_memory() allocate a void* pointer for an object of size 
'Max_Size_In_Storage_Elements. Using some black magic () transform void* 
into an access to T.

See https://groups.google.com/forum/#!topic/comp.lang.ada/-xfDsAOMj5s
about the "black magic" to convert void* to an access.

(I need to use 'Max_Size_In_Storage_Elements for allocation size to be sure 
assignment to my object won't overflow anything, right?)

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 04:53, Victor Porton wrote:
>> It is impossible to properly implement an allocator through a C function
>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>> struct and returns the pointer to the allocated struct.
>> 
>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>> integral multiple of D'Alignment..."
>> 
>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>> would be able just to check (in Allocate procedure implementation) that
>> 
>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>> -- where Dummy_Record is an arbitrary C-convention record
>> -- (as all C records have the same alignment reqs)
>> 
>> So Alignment parameter may be arbitrarily big and the C function
>> alignment may not conform to it.
> 
> Usually allocators return addresses already rounded and there is nothing
> to worry about.
> 
>> Let us think how to work around (in Ada 202x) of this design flaw.
> 
> If any it is _alloc_memory() flaw, not Ada's.

It is an Ada flaw, because Ada must be able to interact with legacy C 
libraries.

> Add max alignment + log max alignment - 1 to the desired size. Add log
> max alignment to the returned address and round to the required
> alignment. Place the offset to original address in front (log alignment
> length). Return the rounded address. When freed use the stored offset to
> get the original address.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Victor Porton wrote:

> Dmitry A. Kazakov wrote:
> 
>> On 2017-10-14 04:53, Victor Porton wrote:
>>> It is impossible to properly implement an allocator through a C function
>>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>>> struct and returns the pointer to the allocated struct.
>>> 
>>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>>> integral multiple of D'Alignment..."
>>> 
>>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>>> would be able just to check (in Allocate procedure implementation) that
>>> 
>>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>>> -- where Dummy_Record is an arbitrary C-convention record
>>> -- (as all C records have the same alignment reqs)
>>> 
>>> So Alignment parameter may be arbitrarily big and the C function
>>> alignment may not conform to it.
>> 
>> Usually allocators return addresses already rounded and there is nothing
>> to worry about.
>> 
>>> Let us think how to work around (in Ada 202x) of this design flaw.
>> 
>> If any it is _alloc_memory() flaw, not Ada's.
> 
> It is an Ada flaw, because Ada must be able to interact with legacy C
> libraries.

Moreover, the same logic would lead to say that there is malloc() standard C 
flaw.

It is not constructive to criticize an ISO standard of C.

>> Add max alignment + log max alignment - 1 to the desired size. Add log
>> max alignment to the returned address and round to the required
>> alignment. Place the offset to original address in front (log alignment
>> length). Return the rounded address. When freed use the stored offset to
>> get the original address.
> 
-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Victor Porton wrote:

> Victor Porton wrote:
> 
>> Dmitry A. Kazakov wrote:
>> 
>>> On 2017-10-14 04:53, Victor Porton wrote:
>>>> It is impossible to properly implement an allocator through a C
>>>> function (such as raptor_alloc_memory() from Raptor C library) which
>>>> allocates a struct and returns the pointer to the allocated struct.
>>>> 
>>>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>>>> integral multiple of D'Alignment..."
>>>> 
>>>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>>>> would be able just to check (in Allocate procedure implementation) that
>>>> 
>>>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>>>> -- where Dummy_Record is an arbitrary C-convention record
>>>> -- (as all C records have the same alignment reqs)
>>>> 
>>>> So Alignment parameter may be arbitrarily big and the C function
>>>> alignment may not conform to it.
>>> 
>>> Usually allocators return addresses already rounded and there is nothing
>>> to worry about.
>>> 
>>>> Let us think how to work around (in Ada 202x) of this design flaw.
>>> 
>>> If any it is _alloc_memory() flaw, not Ada's.
>> 
>> It is an Ada flaw, because Ada must be able to interact with legacy C
>> libraries.
> 
> Moreover, the same logic would lead to say that there is malloc() standard
> C flaw.
> 
> It is not constructive to criticize an ISO standard of C.

I mean, it is because we cannot change C standard for better compatibility 
with Ada. But we can change Ada 202x for better compatibility with C 
libraries.

>>> Add max alignment + log max alignment - 1 to the desired size. Add log
>>> max alignment to the returned address and round to the required
>>> alignment. Place the offset to original address in front (log alignment
>>> length). Return the rounded address. When freed use the stored offset to
>>> get the original address.
>> 
-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 15:52, Victor Porton wrote:

>> Add max alignment + log max alignment - 1 to the desired size. Add log
>> max alignment to the returned address and round to the required
>> alignment. Place the offset to original address in front (log alignment
>> length). Return the rounded address. When freed use the stored offset to
>> get the original address.
> 
> Is "log" logarithm? Why do we need a logarithm?

This is how you calculate the number of storage elements needed to store 
an integer number logN (M), where N is the unit, e.g. 2.

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

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 16:03, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
>> On 2017-10-14 04:53, Victor Porton wrote:
>>> It is impossible to properly implement an allocator through a C function
>>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>>> struct and returns the pointer to the allocated struct.
>>>
>>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>>> integral multiple of D'Alignment..."
>>>
>>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>>> would be able just to check (in Allocate procedure implementation) that
>>>
>>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>>> -- where Dummy_Record is an arbitrary C-convention record
>>> -- (as all C records have the same alignment reqs)
>>>
>>> So Alignment parameter may be arbitrarily big and the C function
>>> alignment may not conform to it.
>>
>> Usually allocators return addresses already rounded and there is nothing
>> to worry about.
>>
>>> Let us think how to work around (in Ada 202x) of this design flaw.
>>
>> If any it is _alloc_memory() flaw, not Ada's.
>>
>> Add max alignment + log max alignment - 1 to the desired size. Add log
>> max alignment to the returned address and round to the required
>> alignment. Place the offset to original address in front (log alignment
>> length). Return the rounded address. When freed use the stored offset to
>> get the original address.
> 
> As far as I understand, it will not work, because the C library I am writing
> bindings for may try to free an object allocated by me (or I my need to free
> an object allocated by the library).

The last sentence describes freeing memory, i.e. for Deallocate.

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

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 16:12, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
>> If any it is _alloc_memory() flaw, not Ada's.
> 
> It is an Ada flaw, because Ada must be able to interact with legacy C
> libraries.

You can call _alloc_memory, where is a problem?

If _alloc_memory() does not respect target platform restrictions, how is 
that Ada's problem?

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

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

>> If the C struct needs alignment greater than that of the elements of
>> which it is composed (see the AI for example) it would have it.
>
> "it would have it"? What this sequence of English words mean?

it would have such an alignment

  struct chrs {
    char c[10];
  }

only *needs* alignment of 1

  struct chrs {
    int last;
    char c[256];
  }

needs the alignment of int (4 on this Mac)

(aploogies if the C isn't correct)

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 16:24, Victor Porton wrote:

> I mean, it is because we cannot change C standard for better compatibility
> with Ada. But we can change Ada 202x for better compatibility with C
> libraries.

There is nothing incompatible in what you described.

There are many C libraries (most?) which cannot deal with objects 
allocated outside, e.g. in an Ada pool. There was never a big problem to 
communicate with such libraries.

The only design flaw Ada has is what Simon referenced to [*]. This is 
specific to unconstrained Ada arrays which are incompatible with C anyway.

------------------
* Array address is the address of the first array element rather than 
the address of the array object.

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

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>>> If the C struct needs alignment greater than that of the elements of
>>> which it is composed (see the AI for example) it would have it.
>>
>> "it would have it"? What this sequence of English words mean?
> 
> it would have such an alignment
> 
>   struct chrs {
>     char c[10];
>   }
> 
> only *needs* alignment of 1
> 
>   struct chrs {
>     int last;
>     char c[256];
>   }

No, all C structs share the same alignment.

> needs the alignment of int (4 on this Mac)
> 
> (aploogies if the C isn't correct)
-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 16:12, Victor Porton wrote:
>> Dmitry A. Kazakov wrote:
>> 
>>> If any it is _alloc_memory() flaw, not Ada's.
>> 
>> It is an Ada flaw, because Ada must be able to interact with legacy C
>> libraries.
> 
> You can call _alloc_memory, where is a problem?
> 
> If _alloc_memory() does not respect target platform restrictions, how is
> that Ada's problem?

The Ada problem is that that _alloc_memory() cannot be integrated with Ada 
allocators. The problem is that (in principle) Ada may request a greater 
alignment than C ever has, and this way Ada allocators become incompatible 
with C.

Note that I filed a request to change the RM about allocators.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 16:24, Victor Porton wrote:
> 
>> I mean, it is because we cannot change C standard for better
>> compatibility with Ada. But we can change Ada 202x for better
>> compatibility with C libraries.
> 
> There is nothing incompatible in what you described.
> 
> There are many C libraries (most?) which cannot deal with objects
> allocated outside, e.g. in an Ada pool. There was never a big problem to
> communicate with such libraries.

I want to create an Ada pool which does the same (de)allocation as a C 
library.

The problem is that creating such a pool is (seemingly) impossible with 
current Ada RM.

> The only design flaw Ada has is what Simon referenced to [*]. This is
> specific to unconstrained Ada arrays which are incompatible with C anyway.
> 
> ------------------
> * Array address is the address of the first array element rather than
> the address of the array object.
> 
-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 16:03, Victor Porton wrote:
>> Dmitry A. Kazakov wrote:
>> 
>>> On 2017-10-14 04:53, Victor Porton wrote:
>>>> It is impossible to properly implement an allocator through a C
>>>> function (such as raptor_alloc_memory() from Raptor C library) which
>>>> allocates a struct and returns the pointer to the allocated struct.
>>>>
>>>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>>>> integral multiple of D'Alignment..."
>>>>
>>>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>>>> would be able just to check (in Allocate procedure implementation) that
>>>>
>>>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>>>> -- where Dummy_Record is an arbitrary C-convention record
>>>> -- (as all C records have the same alignment reqs)
>>>>
>>>> So Alignment parameter may be arbitrarily big and the C function
>>>> alignment may not conform to it.
>>>
>>> Usually allocators return addresses already rounded and there is nothing
>>> to worry about.
>>>
>>>> Let us think how to work around (in Ada 202x) of this design flaw.
>>>
>>> If any it is _alloc_memory() flaw, not Ada's.
>>>
>>> Add max alignment + log max alignment - 1 to the desired size. Add log
>>> max alignment to the returned address and round to the required
>>> alignment. Place the offset to original address in front (log alignment
>>> length). Return the rounded address. When freed use the stored offset to
>>> get the original address.
>> 
>> As far as I understand, it will not work, because the C library I am
>> writing bindings for may try to free an object allocated by me (or I my
>> need to free an object allocated by the library).
> 
> The last sentence describes freeing memory, i.e. for Deallocate.

I again state that we need the C function *_free() to free memory. But it is 
impossible in your scenario, because you change the pointer to point to 
another byte of memory.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> The Ada problem is that that _alloc_memory() cannot be integrated with Ada 
> allocators. The problem is that (in principle) Ada may request a greater 
> alignment than C ever has, and this way Ada allocators become incompatible 
> with C.

I just don't understand what the problem is.

If you declared an access type in Ada and invoked new, it's possible
(really only in the context of the AI I referenced earlier) that the
allocation might require an alignment greater than that required for the
basic data. The AI's first example is

       type T is access String;
       for T'Storage_Pool use ... ;
       X : T := new String'("abc");

    In the case of an access type whose designated subtype is an
    unconstrained array subtype, some implementations prepend contiguous
    dope information to the allocated array. String'Alignment is
    typically 1. If the dope information contains values of the array
    type's index type(s), then the alignment requirement of this dope
    information might reasonably be that of the most strictly aligned
    index type. The given example might be easier to implement if the
    implementation were allowed to pass Integer'Alignment instead of
    String'Alignment as the Alignment parameter in the call to Allocate
    associated with the allocator.

If you then called Unchecked_Deallocation, it would need to be aware of
this extra dope information.

But you don't propose to invoke new, which means that
System.Storage_Pools.Allocate isn't going to be called. You're going to
get C to allocate the memory as appropriate for whatever it contains,
including any dope information, and if the Ada side gets to see its
contents it will do so via appropriate representation clauses, which
will explicitly include any dope information.

I agree that if the C side allocates the memory with an alignment that's
incompatible with the contents of the struct then you'll have a problem,
but I don't see how that could possibly be cured from the Ada side.

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 17:18, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
>> On 2017-10-14 16:03, Victor Porton wrote:
>>> Dmitry A. Kazakov wrote:
>>>
>>>> When freed use the stored offset to
                 ^^^^^^^^^^^^^^^^^^^^^^^^
>>>> get the original address.
      ^^^^^^^^^^^^^^^^^^^^^^^^

>>> As far as I understand, it will not work, because the C library I am
>>> writing bindings for may try to free an object allocated by me (or I my
>>> need to free an object allocated by the library).
>>
>> The last sentence describes freeing memory, i.e. for Deallocate.
> 
> I again state that we need the C function *_free() to free memory. But it is
> impossible in your scenario, because you change the pointer to point to
> another byte of memory.

Re-read the last sentence of my response.

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

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 17:17, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
>> On 2017-10-14 16:24, Victor Porton wrote:
>>
>>> I mean, it is because we cannot change C standard for better
>>> compatibility with Ada. But we can change Ada 202x for better
>>> compatibility with C libraries.
>>
>> There is nothing incompatible in what you described.
>>
>> There are many C libraries (most?) which cannot deal with objects
>> allocated outside, e.g. in an Ada pool. There was never a big problem to
>> communicate with such libraries.
> 
> I want to create an Ada pool which does the same (de)allocation as a C
> library.
> 
> The problem is that creating such a pool is (seemingly) impossible with
> current Ada RM.

It is possible as I explained. You allocate additional information in 
front of the object and shift address. Upon deallocation you use that 
information to shift the address back before passing it to C's free. The 
same technique is used when handling Ada's array address issue in Simple 
Components.

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

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> Simon Wright wrote:
>
>> Victor Porton <porton@narod.ru> writes:
>> 
>>>> If the C struct needs alignment greater than that of the elements of
>>>> which it is composed (see the AI for example) it would have it.
>>>
>>> "it would have it"? What this sequence of English words mean?
>> 
>> it would have such an alignment
>> 
>>   struct chrs {
>>     char c[10];
>>   }
>> 
>> only *needs* alignment of 1
>> 
>>   struct chrs {
>>     int last;
>>     char c[256];
>>   }
>
> No, all C structs share the same alignment.

I agree that malloc() will always allocate aligned on some boundary
(16-byte? 32-byte?) but that's not the same as the alignment of the
struct itself.

See e.g.
https://en.wikipedia.org/wiki/Data_structure_alignment#Typical_alignment_of_C_structs_on_x86

>> needs the alignment of int (4 on this Mac)
>> 
>> (aploogies if the C isn't correct)

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> As far as I understand, it will not work, because the C library I am
> writing bindings for may try to free an object allocated by me (or I
> my need to free an object allocated by the library).

This vital info wasn't part of your original problem statement.

I suppose you might just get away with creating a storage pool backed up
by raptor_alloc_memory() (and corresponding free). But you'd have to
cope with the alignment issue as Dmitry has suggested.

Is the Ada side meant to understand things allocated on the C side? If
so, you'll need to specify the representation exactly.

Is the C side meant to understand things allocated on the Ada side?
Likewise (and no room for hidden dope vectors!)

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>> Simon Wright wrote:
>>
>>> Victor Porton <porton@narod.ru> writes:
>>> 
>>>>> If the C struct needs alignment greater than that of the elements of
>>>>> which it is composed (see the AI for example) it would have it.
>>>>
>>>> "it would have it"? What this sequence of English words mean?
>>> 
>>> it would have such an alignment
>>> 
>>>   struct chrs {
>>>     char c[10];
>>>   }
>>> 
>>> only *needs* alignment of 1
>>> 
>>>   struct chrs {
>>>     int last;
>>>     char c[256];
>>>   }
>>
>> No, all C structs share the same alignment.
> 
> I agree that malloc() will always allocate aligned on some boundary
> (16-byte? 32-byte?) but that's not the same as the alignment of the
> struct itself.
> 
> See e.g.
> 
https://en.wikipedia.org/wiki/Data_structure_alignment#Typical_alignment_of_C_structs_on_x86

I want my program to work well with every conformant Ada compiler, not just 
"typically" as you propose.

>>> needs the alignment of int (4 on this Mac)
>>> 
>>> (aploogies if the C isn't correct)
-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>> The Ada problem is that that _alloc_memory() cannot be integrated with
>> Ada allocators. The problem is that (in principle) Ada may request a
>> greater alignment than C ever has, and this way Ada allocators become
>> incompatible with C.
> 
> I just don't understand what the problem is.
> 
> If you declared an access type in Ada and invoked new, it's possible
> (really only in the context of the AI I referenced earlier) that the
> allocation might require an alignment greater than that required for the
> basic data. The AI's first example is
> 
>        type T is access String;
>        for T'Storage_Pool use ... ;
>        X : T := new String'("abc");

The trouble is as follows:

There is nothing in Ada standard to prevent the above "new" operator to 
request 256-byte alignment of the data. (Yes, I know this does not happen in 
practice, but it is not forbidden by the RM.)

If it requests such a great alignment by the C function *_alloc_memory() is 
able to do only 16-byte alignment, then my allocator would break the 
contract, that is allocate with lesser alignment than requested.

This could in principle lead to undefined behavior.

>     In the case of an access type whose designated subtype is an
>     unconstrained array subtype, some implementations prepend contiguous
>     dope information to the allocated array. String'Alignment is
>     typically 1. If the dope information contains values of the array
>     type's index type(s), then the alignment requirement of this dope
>     information might reasonably be that of the most strictly aligned
>     index type. The given example might be easier to implement if the
>     implementation were allowed to pass Integer'Alignment instead of
>     String'Alignment as the Alignment parameter in the call to Allocate
>     associated with the allocator.

The above quotation is unrelated.

> If you then called Unchecked_Deallocation, it would need to be aware of
> this extra dope information.

Again unrelated.

> But you don't propose to invoke new, which means that

Why? I do propose to invoke new.

> System.Storage_Pools.Allocate isn't going to be called. You're going to
> get C to allocate the memory as appropriate for whatever it contains,

What I want is to write Allocate in such a way that it could work calling 
the C allocating function.

> including any dope information, and if the Ada side gets to see its
> contents it will do so via appropriate representation clauses, which
> will explicitly include any dope information.
> 
> I agree that if the C side allocates the memory with an alignment that's
> incompatible with the contents of the struct then you'll have a problem,
> but I don't see how that could possibly be cured from the Ada side.

"C side" allocated memory compatible with every C struct. This is not the 
problem.

The problem that Ada may request a greater (a natural number of times) 
alignment and the C function cannot do what Ada requests.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 17:17, Victor Porton wrote:
>> Dmitry A. Kazakov wrote:
>> 
>>> On 2017-10-14 16:24, Victor Porton wrote:
>>>
>>>> I mean, it is because we cannot change C standard for better
>>>> compatibility with Ada. But we can change Ada 202x for better
>>>> compatibility with C libraries.
>>>
>>> There is nothing incompatible in what you described.
>>>
>>> There are many C libraries (most?) which cannot deal with objects
>>> allocated outside, e.g. in an Ada pool. There was never a big problem to
>>> communicate with such libraries.
>> 
>> I want to create an Ada pool which does the same (de)allocation as a C
>> library.
>> 
>> The problem is that creating such a pool is (seemingly) impossible with
>> current Ada RM.
> 
> It is possible as I explained. You allocate additional information in
> front of the object and shift address. Upon deallocation you use that
> information to shift the address back before passing it to C's free. The
> same technique is used when handling Ada's array address issue in Simple
> Components.

Again:

You propose to allocate some additional data before value of a C struct T.

But then I cannot pass the allocated pointer to C functions, instead I pass 
the pointer + some shift value.

But C side may call a *_free() function on the passed pointer. If the 
pointer after shifting is different than before shifting, then *_free() 
would do a very wrong thing!

This way, what you have proposed is not a solution.

I decided that I will remove allocator code (because it cannot be guaranteed 
to work) and (quote from my above message):

---

Let the (C compatible) type of the struct be T.

Using raptor_alloc_memory() allocate a void* pointer for an object of size 
'Max_Size_In_Storage_Elements. Using some black magic () transform void* 
into an access to T.

See https://groups.google.com/forum/#!topic/comp.lang.ada/-xfDsAOMj5s
about the "black magic" to convert void* to an access.

(I need to use 'Max_Size_In_Storage_Elements for allocation size to be sure 
assignment to my object won't overflow anything, right?)

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>> As far as I understand, it will not work, because the C library I am
>> writing bindings for may try to free an object allocated by me (or I
>> my need to free an object allocated by the library).
> 
> This vital info wasn't part of your original problem statement.
> 
> I suppose you might just get away with creating a storage pool backed up
> by raptor_alloc_memory() (and corresponding free). But you'd have to
> cope with the alignment issue as Dmitry has suggested.
> 
> Is the Ada side meant to understand things allocated on the C side? If
> so, you'll need to specify the representation exactly.
> 
> Is the C side meant to understand things allocated on the Ada side?
> Likewise (and no room for hidden dope vectors!)

Yes, both sides need to understand struct layout.

This is not a trouble at all: I just add Convention=>C to the record.

We can know the alignment of the struct (just T'Alignment). The trouble is 
that Ada may request allocator to allocate with alignment a (nonzero) 
natural number times more than T'Alignment. This may fail as the requested 
alignment in principle can be greater than the real alignment the C 
*_alloc() function does. This is a real trouble.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 17:18, Victor Porton wrote:
>> Dmitry A. Kazakov wrote:
>> 
>>> On 2017-10-14 16:03, Victor Porton wrote:
>>>> Dmitry A. Kazakov wrote:
>>>>
>>>>> When freed use the stored offset to
>                  ^^^^^^^^^^^^^^^^^^^^^^^^
>>>>> get the original address.
>       ^^^^^^^^^^^^^^^^^^^^^^^^
> 
>>>> As far as I understand, it will not work, because the C library I am
>>>> writing bindings for may try to free an object allocated by me (or I my
>>>> need to free an object allocated by the library).
>>>
>>> The last sentence describes freeing memory, i.e. for Deallocate.
>> 
>> I again state that we need the C function *_free() to free memory. But it
>> is impossible in your scenario, because you change the pointer to point
>> to another byte of memory.
> 
> Re-read the last sentence of my response.

No Dmitry, you don't understand me.

We may pass the allocated address to a C function.

1. This C function may need to get some data from the struct. In this case 
we need to pass into C the shifted address.

2. This C function may call *_free() with the address of the struct. In this 
case we need to pass into C the original allocation address.

Thus the same address we pass into a C function is both original and 
shifted. This is a clear contradiction.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 18:34, Victor Porton wrote:
> Dmitry A. Kazakov wrote:
> 
>> On 2017-10-14 17:17, Victor Porton wrote:
>>> Dmitry A. Kazakov wrote:
>>>
>>>> On 2017-10-14 16:24, Victor Porton wrote:
>>>>
>>>>> I mean, it is because we cannot change C standard for better
>>>>> compatibility with Ada. But we can change Ada 202x for better
>>>>> compatibility with C libraries.
>>>>
>>>> There is nothing incompatible in what you described.
>>>>
>>>> There are many C libraries (most?) which cannot deal with objects
>>>> allocated outside, e.g. in an Ada pool. There was never a big problem to
>>>> communicate with such libraries.
>>>
>>> I want to create an Ada pool which does the same (de)allocation as a C
>>> library.
>>>
>>> The problem is that creating such a pool is (seemingly) impossible with
>>> current Ada RM.
>>
>> It is possible as I explained. You allocate additional information in
>> front of the object and shift address. Upon deallocation you use that
>> information to shift the address back before passing it to C's free. The
>> same technique is used when handling Ada's array address issue in Simple
>> Components.
> 
> Again:
> 
> You propose to allocate some additional data before value of a C struct T.
> 
> But then I cannot pass the allocated pointer to C functions, instead I pass
> the pointer + some shift value.

No. Address is passed to Ada.

There is no reason to pass any Ada pointers to any C functions except 
than in the form of "user data".

> But C side may call a *_free() function on the passed pointer. If the
> pointer after shifting is different than before shifting, then *_free()
> would do a very wrong thing!

No it cannot. You cannot deallocate any Ada objects from C because they 
require finalization.

A custom Ada storage pool backed by whatever C memory management library 
is perfectly possible even of C cannot handle alignment. As I explained 
Addresses are shifted forth and back between malloc-Allocate and 
Deallocate-free pairs.

Any other method of interaction is simply illegal because of 
finalization issues. If an object must be freed by C, it must a C 
object. If that is necessary, then for each C object an Ada object is 
created. See GtkAda for an example how such situations are handled.

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

Re: Allocators design flaw

[Victor Porton]

Dmitry A. Kazakov wrote:

> On 2017-10-14 18:34, Victor Porton wrote:
>> Dmitry A. Kazakov wrote:
>> 
>>> On 2017-10-14 17:17, Victor Porton wrote:
>>>> Dmitry A. Kazakov wrote:
>>>>
>>>>> On 2017-10-14 16:24, Victor Porton wrote:
>>>>>
>>>>>> I mean, it is because we cannot change C standard for better
>>>>>> compatibility with Ada. But we can change Ada 202x for better
>>>>>> compatibility with C libraries.
>>>>>
>>>>> There is nothing incompatible in what you described.
>>>>>
>>>>> There are many C libraries (most?) which cannot deal with objects
>>>>> allocated outside, e.g. in an Ada pool. There was never a big problem
>>>>> to communicate with such libraries.
>>>>
>>>> I want to create an Ada pool which does the same (de)allocation as a C
>>>> library.
>>>>
>>>> The problem is that creating such a pool is (seemingly) impossible with
>>>> current Ada RM.
>>>
>>> It is possible as I explained. You allocate additional information in
>>> front of the object and shift address. Upon deallocation you use that
>>> information to shift the address back before passing it to C's free. The
>>> same technique is used when handling Ada's array address issue in Simple
>>> Components.
>> 
>> Again:
>> 
>> You propose to allocate some additional data before value of a C struct
>> T.
>> 
>> But then I cannot pass the allocated pointer to C functions, instead I
>> pass the pointer + some shift value.
> 
> No. Address is passed to Ada.

The address is passed to Ada, but I also need to pass the pointer to C.

> There is no reason to pass any Ada pointers to any C functions except
> than in the form of "user data".

Convention=>C accesses to records ARE passed to C functions.

Sometimes we even don't know what is inside the records passed to C by a 
pointer.

Then we can use:

type Dummy_Record is null record with Convention=>C;

It is quite legit to pass (Convention=>C) pointers to Dummy_Record, and I do 
this a lot.

So your "There is no reason to pass any Ada pointers to any C functions" is 
wrong.

>> But C side may call a *_free() function on the passed pointer. If the
>> pointer after shifting is different than before shifting, then *_free()
>> would do a very wrong thing!
> 
> No it cannot. You cannot deallocate any Ada objects from C because they
> require finalization.

Convention=>C objects do not require finalization.

> A custom Ada storage pool backed by whatever C memory management library
> is perfectly possible even of C cannot handle alignment. As I explained
> Addresses are shifted forth and back between malloc-Allocate and
> Deallocate-free pairs.

See my other message. You do not understand me.

> Any other method of interaction is simply illegal because of
> finalization issues. If an object must be freed by C, it must a C
> object. If that is necessary, then for each C object an Ada object is
> created. See GtkAda for an example how such situations are handled.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Dmitry A. Kazakov]

On 2017-10-14 19:24, Victor Porton wrote:

> The address is passed to Ada, but I also need to pass the pointer to C.

You didn't explained what you needed. So far you complained about Ada 
storage pool backed by a C pool. This is no problem.

The rule is simple, anything allocated in Ada pool never goes as a 
managed pointer back to C.

>> There is no reason to pass any Ada pointers to any C functions except
>> than in the form of "user data".
> 
> Convention=>C accesses to records ARE passed to C functions.

How is that Ada pointer? You confuse convention (Of a type 
representation? Of parameter parameter passing?) with memory management.

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

Re: Allocators design flaw

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> There is nothing in Ada standard to prevent the above "new" operator
> to request 256-byte alignment of the data. (Yes, I know this does not
> happen in practice, but it is not forbidden by the RM.)
>
> If it requests such a great alignment by the C function
> *_alloc_memory() is able to do only 16-byte alignment, then my
> allocator would break the contract, that is allocate with lesser
> alignment than requested.

Since you agree it's very unlikely that an Ada compiler would actually
do that, why not just check the requested alignment & raise PE if it's
too large?

Re: Allocators design flaw

[Victor Porton]

Simon Wright wrote:

> Victor Porton <porton@narod.ru> writes:
> 
>> There is nothing in Ada standard to prevent the above "new" operator
>> to request 256-byte alignment of the data. (Yes, I know this does not
>> happen in practice, but it is not forbidden by the RM.)
>>
>> If it requests such a great alignment by the C function
>> *_alloc_memory() is able to do only 16-byte alignment, then my
>> allocator would break the contract, that is allocate with lesser
>> alignment than requested.
> 
> Since you agree it's very unlikely that an Ada compiler would actually
> do that, why not just check the requested alignment & raise PE if it's
> too large?

I already considered this, but:

It does not seem absolutely impossible that Ada never requests alignment 
above the minimum alignment for allocated C structs. (And all we can know 
about the allocator in the C library is that it is appropriate for structs.)

For example 4 bytes seems a possible alignment for C structs, but I can't be 
completely sure that Ada never requests 8 bytes alignment.

Yes, this is unlikely, but not entirely impossible.

So I have rewritten my code without using allocators at all.

-- 
Victor Porton - http://portonvictor.org

Re: Allocators design flaw

[Randy Brukardt]

"Victor Porton" <porton@narod.ru> wrote in message 
news:ort609$1i31$2@gioia.aioe.org...
> Dmitry A. Kazakov wrote:
>
>> On 2017-10-14 04:53, Victor Porton wrote:
>>> It is impossible to properly implement an allocator through a C function
>>> (such as raptor_alloc_memory() from Raptor C library) which allocates a
>>> struct and returns the pointer to the allocated struct.
>>>
>>> It is because RM13.11(21.5/3) "The Alignment parameter is a nonzero
>>> integral multiple of D'Alignment..."
>>>
>>> (If it were "The Alignment parameter is equal to D'Alignment", then we
>>> would be able just to check (in Allocate procedure implementation) that
>>>
>>> pragma Assert(Dummy_Record'Alignment mod Alignment = 0);
>>> -- where Dummy_Record is an arbitrary C-convention record
>>> -- (as all C records have the same alignment reqs)
>>>
>>> So Alignment parameter may be arbitrarily big and the C function
>>> alignment may not conform to it.
>>
>> Usually allocators return addresses already rounded and there is nothing
>> to worry about.
>>
>>> Let us think how to work around (in Ada 202x) of this design flaw.
>>
>> If any it is _alloc_memory() flaw, not Ada's.
>
> It is an Ada flaw, because Ada must be able to interact with legacy C
> libraries.

Ada can interact just fine with C libraries. But there was never any 
intention that allocators and storage pools would be part of that 
interaction. It seems to be the case here that you are trying to fit a 
square peg into a round hole.

Keep in mind that all C interfacing is by definition implementation-defined, 
since it depends heavily on the C compiler. There's only so much portability 
that can be achieved in such interfacing; it can never be 100%.

                                Randy. 

Re: Allocators design flaw

[David Thompson]

On Sat, 14 Oct 2017 16:56:04 +0100, Simon Wright <simon@pushface.org>
wrote:

> Victor Porton <porton@narod.ru> writes:
> 
> > Simon Wright wrote:
<snip>
> >>   struct chrs {
> >>     char c[10];
> >>   }
> >> 
> >> only *needs* alignment of 1
> >> 
> >>   struct chrs {
> >>     int last;
> >>     char c[256];
> >>   }
> >
> > No, all C structs share the same alignment.
> 
That's quite wrong. No C standard has ever required it, and I've used
several conforming C implementations where different struct types have
different alignments. 

There are restrictions on _pointers to structs_ (and unions) as I've
just described in another post, but not the structs/unions themselves.

> I agree that malloc() will always allocate aligned on some boundary
> (16-byte? 32-byte?) but that's not the same as the alignment of the
> struct itself.
> 
malloc (and calloc and realloc) are required to provide the 'maximal'
alignment of _any_ type supported by the compiler (which I've never
seen more than 8 bytes) and allowed to provide more if they want, for
example because it is sometimes beneficial (like SSE data on x86) or
because the allocator strategy works better (maybe buddy).

> See e.g.
> https://en.wikipedia.org/wiki/Data_structure_alignment#Typical_alignment_of_C_structs_on_x86
> 
Don't need typical, this is in the standard.