Reference counting and idempotent finalize

Reference counting and idempotent finalize

[Natasha Kerensikova]

Hello,

I have recently reinvented the reference counted wheel, and been told
that I got it all wrong because Finalize must be idempotent. However I
already diffusely knew that, though I cannot remember from where it
comes or whether I thought of it as a hard requirement or only as a good
practice (the difference is hard to tell when such a rule is
internalized).

Anyway, my naive implementation looks like that:

   procedure Finalize (Self : in out Reference) is
   begin
      Release (Self.Access_Value);
   end Finalize;

   procedure Release (Access_Value : in out Access_To_Actual_Data) is
   begin
      if Access_Value /= null then
        Access_Value.all.Counter := Access_Value.all.Counter - 1;

        if Access_Value.all.Counter = 0 then
           Unchecked_Deallocation_Instance (Access_Value);
        else
           Access_Value := null;
        end if;
     end if;
   end Release;

For the reference, I used explicit dereference because in the real code
the parameter is not called Access_Value and is not obviously an access,
so I thought it clearer that way. And the procedure Release is used
because Finalize feels "special" so I don't want to call it myself.

As far as I can see, Access_Value = null could be post condition for
Release, and unless the code flow is interrupted by an exception, that
looks extremely idempotent to me. Am I missing something here?

I neglected the possibility of exceptional flow interruption because I
felt that an exception in Finalize triggers the end of the world (the
same way I've felt for a long time the idempotency requirement). Now
having done the research, 7.6.1(13) doesn't really mention the world
ending, that looks quite close to it, doesn't it?

Am I missing something on the exception part? Or is my implementation
good enough?


Thanks in advance for your help,
Natasha

Re: Reference counting and idempotent finalize

[AdaMagica]

With the little you show, this looks OK.

Be careful about the lifetime of dereferences.

Compare Ada Gems
http://www.adacore.com/adaanswers/gems/gem-97-reference-counting-in-ada-part-1
and
http://www.adacore.com/adaanswers/gems/gem-107-preventing-deallocation-for-reference-counted-types/

Shameless plug: See my implementation
http://www.christ-usch-grein.homepage.t-online.de/Ada/Smart_Pointers.html

Re: Reference counting and idempotent finalize

[Dmitry A. Kazakov]

On Wed, 11 Sep 2013 10:45:37 +0000 (UTC), Natasha Kerensikova wrote:

> Anyway, my naive implementation looks like that:
> 
>    procedure Finalize (Self : in out Reference) is
>    begin
>       Release (Self.Access_Value);
>    end Finalize;
> 
>    procedure Release (Access_Value : in out Access_To_Actual_Data) is
>    begin
>       if Access_Value /= null then
>         Access_Value.all.Counter := Access_Value.all.Counter - 1;
> 
>         if Access_Value.all.Counter = 0 then
>            Unchecked_Deallocation_Instance (Access_Value);
>         else
>            Access_Value := null;
>         end if;
>      end if;
>    end Release;
> 
> For the reference, I used explicit dereference because in the real code
> the parameter is not called Access_Value and is not obviously an access,
> so I thought it clearer that way. And the procedure Release is used
> because Finalize feels "special" so I don't want to call it myself.
> 
> As far as I can see, Access_Value = null could be post condition for
> Release, and unless the code flow is interrupted by an exception, that
> looks extremely idempotent to me. Am I missing something here?
> 
> I neglected the possibility of exceptional flow interruption because I
> felt that an exception in Finalize triggers the end of the world (the
> same way I've felt for a long time the idempotency requirement). Now
> having done the research, 7.6.1(13) doesn't really mention the world
> ending, that looks quite close to it, doesn't it?
> 
> Am I missing something on the exception part? Or is my implementation
> good enough?

It looks OK, but do not forget Adjust.

Also you might wish add a check against negative reference count.

You could make an alternative version for debug scenario which keeps track
of all changes of the reference count dumping them on errors. GNAT stack
trace is handy for that. Do not trust reference counting, it is an endless
source of many hideous errors even if the implementation of is correct.

Tracing for the latest exception when in Finalize (GNAT functionality) is
extremely helpful as well, because upon error propagation you get a
snowball of cascading exceptions hiding the original problem. Always kill
any exceptions in Finalize and do an emergency tracing in the handler.

Yet another version is likely needed for tasking, that is when the
reference objects are used concurrently, so that the reference count is
updated concurrently. You will need a protected object to handle increments
and decrements and careful design preventing concurrent increments when the
count reached 0.

One possible implementation can be found here:

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

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

Re: Reference counting and idempotent finalize

[Dmitry A. Kazakov]

On Wed, 11 Sep 2013 10:45:37 +0000 (UTC), Natasha Kerensikova wrote:

>    procedure Release (Access_Value : in out Access_To_Actual_Data) is
>    begin
>       if Access_Value /= null then
>         Access_Value.all.Counter := Access_Value.all.Counter - 1;

A minor stylistic issue, you don't need .all in order to access components:

           Access_Value.Counter := Access_Value.Counter - 1;

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

Re: Reference counting and idempotent finalize

[Jeffrey R. Carter]

On 09/11/2013 03:45 AM, Natasha Kerensikova wrote:
>          Access_Value.all.Counter := Access_Value.all.Counter - 1;

What happens if Counter is already zero? Can Counter become negative, and if so, what does it mean for Counter to be 
negative?

> I neglected the possibility of exceptional flow interruption because I
> felt that an exception in Finalize triggers the end of the world (the
> same way I've felt for a long time the idempotency requirement). Now
> having done the research, 7.6.1(13) doesn't really mention the world
> ending, that looks quite close to it, doesn't it?

ARM 7.6.1 says, "It is a bounded error for a call on Finalize or Adjust that occurs as part of object finalization or 
assignment to propagate an exception." My practice has, therefore, been to always ensure that Finalize cannot propagate 
an exception.

FWIW, Finalize from PragmARC.Safe_Pointers looks like

    procedure Finalize (Item : in out Safe_Pointer) is
       procedure Free is new Ada.Unchecked_Deallocation (Object => Safe_Group, Name => Name);
    begin -- Finalize
       if Item.Ptr /= null then
          if Item.Ptr.Count > 0 then
             Item.Ptr.Count := Item.Ptr.Count - 1;
          end if;

          if Item.Ptr.Count = 0 then
             Free (Item.Ptr);
          end if;

          Item.Ptr := null;
       end if;
    end Finalize;

I have convinced myself that this cannot propagate an exception (except Storage_Error, of course, since anything can 
result in Storage_Error). It might be easier (and safer) to always have "exception when others => null;" on every Finalize.

The PragmAda Reusable Components, including the full implementation of PragmARC.Safe_Pointers, are at

pragmada.x10hosting.com

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail

--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

Re: Reference counting and idempotent finalize

[Pascal Obry]

Natasha,

See Gem#97 for an idempotent discussion:

http://www.adacore.com/adaanswers/gems/gem-97-reference-counting-in-ada-part-1/

Pascal.


-- 
  Pascal Obry /  Magny Les Hameaux (78)

  The best way to travel is by means of imagination

  http://v2p.fr.eu.org
  http://www.obry.net

  gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: Reference counting and idempotent finalize

[Simon Wright]

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

> ARM 7.6.1 says, "It is a bounded error for a call on Finalize or
> Adjust that occurs as part of object finalization or assignment to
> propagate an exception." My practice has, therefore, been to always
> ensure that Finalize cannot propagate an exception.

If one of my programs were to raise an exception in Finalize it would be
because I hadn't understood the problem - or because Storage_Error - and
in either case it wouldn't be safe to continue.

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

On 2013-09-11, Simon Wright <simon@pushface.org> wrote:
> "Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org> writes:
>
>> ARM 7.6.1 says, "It is a bounded error for a call on Finalize or
>> Adjust that occurs as part of object finalization or assignment to
>> propagate an exception." My practice has, therefore, been to always
>> ensure that Finalize cannot propagate an exception.
>
> If one of my programs were to raise an exception in Finalize it would be
> because I hadn't understood the problem - or because Storage_Error - and
> in either case it wouldn't be safe to continue.

That's roughly the reasoning I had put behind the words "the world ends"
in the OP.

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

On 2013-09-11, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On Wed, 11 Sep 2013 10:45:37 +0000 (UTC), Natasha Kerensikova wrote:
>
>>    procedure Release (Access_Value : in out Access_To_Actual_Data) is
>>    begin
>>       if Access_Value /= null then
>>         Access_Value.all.Counter := Access_Value.all.Counter - 1;
>
> A minor stylistic issue, you don't need .all in order to access components:
>
>            Access_Value.Counter := Access_Value.Counter - 1;
>

I thought addressing it explicitly in the OP would spare me from the
remark.

Even though I don't need .all, and usually skip when not needed, there
are situations like this reference-counting code when I feel the
confusion between objects and accesses to objects is too easy and harms
readability (at least when the reader is me).

The null comparison on the previous line is not enough to recognize at a
glance that Access_Value is indeed an access value, so I knowingly wrote
the optional explicit dereferencing here.

Now I might be a bit biased by my C background, the implicit
dereferencing in Ada feels a lot like the implicit conversion from array
to pointer-to-the-first-element, and from function pointer to function.

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

On 2013-09-11, Pascal Obry <pascal@obry.net> wrote:
> See Gem#97 for an idempotent discussion:
>
> http://www.adacore.com/adaanswers/gems/gem-97-reference-counting-in-ada-part-1/

Maybe I should have mentioned it explicitly in the OP, but that's
exactly what triggered my posting here.
That and http://sourceforge.net/p/booch95/bugs/26/ too.

And I still don't see any clue on why their code is more idempotent than
mine.

Again, what am I missing here?

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

On 2013-09-11, Jeffrey R. Carter <spam.jrcarter.not@spam.acm.org> wrote:
> On 09/11/2013 03:45 AM, Natasha Kerensikova wrote:
>>          Access_Value.all.Counter := Access_Value.all.Counter - 1;
>
> What happens if Counter is already zero? Can Counter become negative,
> and if so, what does it mean for Counter to be negative?

If Counter is already zero, a range check fails, an exception is
propagated, and the world ends.

A negative value of Counter would mean something is seriously wrong with
the compiler or the memory has been corrupted. If I can't trust a
variable to be within the range defined for its type, I probably can't
trust the system to perform any meaningful computation.

> FWIW, Finalize from PragmARC.Safe_Pointers looks like
>
>     [...]

I genuinely don't see any difference between this and my code, except
for my range check (but if it fails I do want the world to end), and
that you cover the possibility of Unchecked_Deallocation not setting the
access to null. Is this really possible?

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

On 2013-09-11, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> You could make an alternative version for debug scenario which keeps track
> of all changes of the reference count dumping them on errors. GNAT stack
> trace is handy for that. Do not trust reference counting, it is an endless
> source of many hideous errors even if the implementation of is correct.

Would you please elaborate on why reference counting shouldn't be
trusted? What dangers am I brazingly exposing myself to?

> Tracing for the latest exception when in Finalize (GNAT functionality) is
> extremely helpful as well, because upon error propagation you get a
> snowball of cascading exceptions hiding the original problem. Always kill
> any exceptions in Finalize and do an emergency tracing in the handler.
>
> Yet another version is likely needed for tasking, that is when the
> reference objects are used concurrently, so that the reference count is
> updated concurrently. You will need a protected object to handle increments
> and decrements and careful design preventing concurrent increments when the
> count reached 0.

All these refinements are way beyond the scope a basic roll-my-own
implementation. If I needed such complexity I wouldn't have tried to
implement it without having thoroughly checked that there is no suitable
implementation already available.

I have roughly the same heuristic for concurrent stuff and for proper
fault recovery as I have for cryptography: never try to code it at home
unless it really does not exist elsewhere yet.

Re: Reference counting and idempotent finalize

[Dmitry A. Kazakov]

On Thu, 12 Sep 2013 05:34:53 +0000 (UTC), Natasha Kerensikova wrote:

> On 2013-09-11, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>> You could make an alternative version for debug scenario which keeps track
>> of all changes of the reference count dumping them on errors. GNAT stack
>> trace is handy for that. Do not trust reference counting, it is an endless
>> source of many hideous errors even if the implementation of is correct.
> 
> Would you please elaborate on why reference counting shouldn't be
> trusted? What dangers am I brazingly exposing myself to?

Because reference counting scheme (and any GC in general) is based on
certain premises to work. These are always difficult to satisfy in a
real-life application. In particular, one that you have no circular
dependencies. The typical approach of breaking them (when you cannot
redesign it otherwise) is having weak references in addition to strong
ones. Consider a tree of nodes where parents refer to children and children
do to the parent. One reference is strong, a backward one must be weak.
That adds another layer of complexity to already messy thing.

The point is actually that problems come from the application domain. So,
time to time, you will have to inspect reference counts even if counting
implementation as such is all OK. Thus it is better to integrate some tools
for this right from the start.

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

Re: Reference counting and idempotent finalize

[Dmitry A. Kazakov]

On Thu, 12 Sep 2013 05:05:27 +0000 (UTC), Natasha Kerensikova wrote:

> A negative value of Counter would mean something is seriously wrong with
> the compiler or the memory has been corrupted.

Yes it happens not very frequently. A far more probable issue when the
count has to be checked against 0 is in the Finalize of counted objects. If
you discover that the count is not zero, that is a serious problem. This
happens very often upon exception propagation when there are still
outstanding references and the compiler calls Finalize because something
(some type for example) goes out for the scope. There is a funny rule that
the compiler has to maintain a list of controlled objects and call Finalize
on its own when you least expect it...

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

Re: Reference counting and idempotent finalize

[sbelmont700]

Suppose there are two shared pointers around, implying a reference count of two.  One of the references is finalized because it goes out of scope, and the count decreases to one.  Then finalize is "mysteriously" called on the first reference a second time, which decreases the count to zero, and deallocates the object.  When you access the still-existing first reference, the data is gone and you get an exception.

However, if you do this:

if not Self.Is_Finalized then
   Release (Self.Access_Value); 
   Self.Is_Finalized := true;
end if;

Then the second finalization does nothing and everything is fine.

The 'mysterious' finalization comes from one of two places.  First, if the "Finalize" procedure is overriden in the public part, a client could explicitly call it whenever they want, and a second 'normal' finalization would be called when it goes out of scope.  

The second problem is if the executing task is aborted during an assignment.  If you do x := y, then first you Finalize x, then copy y into x, and then Adjust the new value of x.  If someone aborts this task after the first finalize starts but before the adjust starts, then the first finalize will complete, the task will be aborted, and then x will be finalized again when all the local objects are finalized.

-sb

Re: Reference counting and idempotent finalize

[Simon Wright]

Natasha Kerensikova <lithiumcat@gmail.com> writes:

> On 2013-09-11, Pascal Obry <pascal@obry.net> wrote:
>> See Gem#97 for an idempotent discussion:
>>
>> http://www.adacore.com/adaanswers/gems/gem-97-reference-counting-in-ada-part-1/
>
> Maybe I should have mentioned it explicitly in the OP, but that's
> exactly what triggered my posting here.
> That and http://sourceforge.net/p/booch95/bugs/26/ too.
>
> And I still don't see any clue on why their code is more idempotent than
> mine.
>
> Again, what am I missing here?

I don't think you're missing anything. Of course my BC code could be
wrong too.

I looked at the GNATColl code; maybe it's age, maybe it was too late at
night, but I couldn't summon up the energy to understand it. And I
don't think I like the way it uses internal packages (but there may be a
good reason for the design).

Re: Reference counting and idempotent finalize

[Pascal Obry]

Natasha,

> Maybe I should have mentioned it explicitly in the OP, but that's
> exactly what triggered my posting here.
> That and http://sourceforge.net/p/booch95/bugs/26/ too.
> 
> And I still don't see any clue on why their code is more idempotent than
> mine.
> 
> Again, what am I missing here?

Nothing I suppose, your code looks idempotent to me. Not coded exactly
the same way, but in all case the Firnalize procedure exit with the
pointer being set to null. That's the important point!

Pascal.

-- 
  Pascal Obry /  Magny Les Hameaux (78)

  The best way to travel is by means of imagination

  http://v2p.fr.eu.org
  http://www.obry.net

  gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: Reference counting and idempotent finalize

[Jeffrey R. Carter]

On 09/11/2013 10:05 PM, Natasha Kerensikova wrote:
>
> If Counter is already zero, a range check fails, an exception is
> propagated, and the world ends.
>
> A negative value of Counter would mean something is seriously wrong with
> the compiler or the memory has been corrupted. If I can't trust a
> variable to be within the range defined for its type, I probably can't
> trust the system to perform any meaningful computation.

I check to ensure that the exception doesn't occur not because I don't trust the compiler, or even memory, but to 
protect against future, incorrect modifications, which I have encountered often enough in the past to worry about. This 
is why my code often checks a Natural for "<= 0", even though that can't happen; it's a habit I developed over 30 yrs 
ago in inferior languages.

> I genuinely don't see any difference between this and my code, except
> for my range check (but if it fails I do want the world to end), and
> that you cover the possibility of Unchecked_Deallocation not setting the
> access to null. Is this really possible?

No. The postcondition for UD is "X = null", and the 1st Ada compiler I used apparently implemented UD as "begin X := 
null; end;". In my case, this is another unnecessarily defensive idiom. The postcondition for Finalize is "Item.Ptr = 
null" and I make sure of that, even if UD misbehaves. Your version could leave Self.Access_Value non-null if the 
decrement fails. In practice they're the same; in theory, not.

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail

--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

Hello,

On 2013-09-11, Natasha Kerensikova <lithiumcat@gmail.com> wrote:
> I have recently reinvented the reference counted wheel, and been told
> that I got it all wrong because Finalize must be idempotent. However I
> already diffusely knew that, though I cannot remember from where it
> comes or whether I thought of it as a hard requirement or only as a good
> practice (the difference is hard to tell when such a rule is
> internalized).
>
> Anyway, my naive implementation looks like that:
>
>    [...]

So I have published the implementation on github (and on a public fossil
repository on my server, but that's nearly as trendy), it's available
at :
https://github.com/faelys/natools/blob/trunk/src/natools-references.ads

One feature it has that I haven't found it most other implementations
mentioned here or found through a web search, is that it places no
requirement on the referenced type.

In particular, it allows creating reference to any existing type without
having to change it, e.g. Ada.Text_IO.File_Type.

The fact that it supports referencing to a limited type is a large part
of my needs. I remember someone here (I think it was Randy) saying that
limited types are a pain and should be avoided in public interfaces, in
favor of a reference-semantic non-limited type. So I declare the
intrinsically limited type in the private part of the specification and
use the reference counter to provide the semantics of the public type.
That's why I haven't found the need yet for weak references or
concurrency.

Any comment about my code is welcome, should anyone take the time to
have a look at it.


Thanks for your help,
Natasha

Re: Reference counting and idempotent finalize

[AdaMagica]

Natasha,

I like this spec - it looks fine on a superficial inspection, and also the body looks fine.

Haven't however executed it (with e.g. tasks as limited objects).

Just one question: Why haven't you applied the Implicit_Dereference aspect to your accessor and mutator?

Re: Reference counting and idempotent finalize

[Natasha Kerensikova]

Hello,

On 2013-09-30, AdaMagica <christ-usch.grein@t-online.de> wrote:
> I like this spec - it looks fine on a superficial inspection, and also
> the body looks fine.

Thanks a lot.

> Haven't however executed it (with e.g. tasks as limited objects).

I have only tested it with a plain limited record. I should try to
incorporate tasks in the test suite, that's a great idea.

> Just one question: Why haven't you applied the Implicit_Dereference
> aspect to your accessor and mutator?

Because the code is currently in Ada 2005, which AFAIK does not support
the aspect. I'm usually using GNAT AUX, which lags behind GNAT FSF,
which itself lags behind GNAT GPL, so I don't really know how much of
Ada 2012 is available to me at the moment.


Natasha