RCArray is unsafe (page 8)

March 03, 2015
Re: RCArray is unsafe
Posted by Biker
in reply to Sativa
Permalink
Biker
Posted in reply to Sativa
Permalink
On Tuesday, 3 March 2015 at 07:17:11 UTC, Sativa wrote:
> On Sunday, 1 March 2015 at 15:44:49 UTC, Marc Schütz wrote:
>> Walter posted an example implementation of a reference counted array [1], that utilizes the features introduced in DIP25 [2]. Then, in the threads about reference counted objects, several people posted examples [3, 4] that broke the suggested optimization of eliding `opAddRef()`/`opRelease()` calls in certain situations.
>>
>> A weakness of the same kind affects DIP25, too. The core of the problem is borrowing (ref return as in DIP25), combined with manual (albeit hidden) memory management. An example to illustrate:
>>
>
>
> 1 >     struct T {
> 2 >         void doSomething();
> 3 >     }
> 4 >     struct S {
> 5 >         RCArray!T array;
> 7 >     }
> 8 >     void main() {
> 9 >         auto s = S(RCArray!T([T()])); // s.array's refcount is
> 10> now 1
> 11>         foo(s, s.array[0]);           // pass by ref
>
>         ++  s.array[0] = myt;             // Would also be invalid
> 12>     }
> 13>     void foo(ref S s, ref T T) {
> 14>         s.array = RCArray!T([]);      // drop the old s.array
> 15>         t.doSomething();              // oops, t is gone
> 16>     }
>
>
>
> 1. Assignment to RC types is not the same as assignments to non-RC types.
> 2. Allocation of RC types is more than just allocating of non-RC types.
>
> Using the above example:
>
> #9: The assignment and allocation does two things:
>    a. Decrements the current RC of s.array(here it is null so no RC is used)
>    b. Increments the ref count of the allocated RCArray by one.
>
> #11: we pass both s and a referent to inside S. This is odd behavior and not technically required in this case(just pass S). Of course, we can't expect such behavior to creep up in complex code.
>
> #14. In this case the behavior is correct. The assignment does the following:
>    a. Decrements the current RC of s.array(here was 1, so now it is 0)
>    b. Increments the current RC of the newly allocated RC array and assigns it to s.array.
>
> #15. Since T refers to the old s.array, which now has a ref count of 0(which we can assume to then be unallocated), line 15 becomes a run-time error.
>
> ---
>
> How to fix?
>
> It seems that the only way to make it work well is to use sort of "lazy" ref counting.
>
> Here references are created at the start of functions and decremented at the end of functions... rather that in place(which then causes problems with things that happen after it).
>
> But this can't work as in the ++ I added. Here it would solve your problem but not fix the a generalization of it.
>
> ---
>
> Is there a solution? Essentially no. Only at the end of the program could we possibly have the last function release all RC counted arrays. Since it is the end of the program it is the only time we can know that no more RC types will be used.
>
> The problem is analogous to the multiple-inheritance problem.
>
> ---
>
> Flow analysis can only help so far(it won't help with dynamically allocated types that are allocated depending on some "random" factor.
>
> ---
>
> Note that since t is pointing to a part of S, technically we can't release s until t is released.
>
> So, effectively, S has to be ref counted too! And it's ref count must check check T's ref count. If it is non-zero then the it can't release itself(or the reference to it's array).
>
> Also, something eventually has to release S(or which is then s.array). When? Well, since t depends on S, it is when t is released. So we would naturally have to inform t that it should too release s when it is released.
>
> ----
>
> So, if that sort of makes sense I'll explain the solution: It might be a bit fuzzy but I'll try to make things very clear. [I will also sometimes conflate the usage of concrete objects and their corresponding abstract types. e.g., "T with t". It should be clear context which is meant. e.g., If I say "T is released", I mean that the object with type T was released. When they need to be distinguished between I will do so(mainly in the code examples]
>
>
> A *reference counted* type, from here on designated as RCT, is a type that only allows itself to be released to the heap when nothing depends on it. [Obviously if anything depends on it when after it is released will fail to be fulfilled]
>
> If a RCT does not contains any references to any RCT's we will call it a free RCT or FRCT. Such types behave in a simple way. They can be free'ed completely immediately. Since FRCT's do not contain any references to other RCT's all their references are simple references that can be free'ed immediately.
>
> We require that if a type contains a reference to a RCT then it too is a RCT. [the relation ContainsRCT(T1,T2) ==> ContainsRCT(T2,T1) ==> Both T1 and T2 are either RCT's or not RCT's] This isn't a big deal but without it we end up requiring all types to be RCT's. Here we allow some types to be not be RCT's.
>
>
> In code,
>
> class T { }   // a standard non-reference counted type.
>               // It can't use any RCT's as references. It is your basic D type of class.
>
> rcclass FRCT  // rcclass means reference counted class. It is identical to your basic
>               // D type of class but has different keyword designator(which is why we call them free).
> {
>   int x;
>   float[] y
>   // etc, FRCT does not point to any RCT's
> }
>
> rcclass X { }  // Just another RCT
>
> rcclass RCT
> {
>     FRCT myFRCT;
>     int y;
>     RCT foo(ref barRCT);
>     X x;
>     // etc Basically this is a class that can include other RCT's
> }
>
> ----
>
> Ultimately we could simply use the basic D class but we would have to designate every type as an RCT type... even the basic types. I'm trying to avoid some basic issues of that method that would derail the discussion. [But for those that want to know: one could simply treat all objects in d as rcclass types describe above, even basic types and such, but optimize out the reference counting part in in the compiler for those basic and FRCT types... this then would simply lead back to the method I'm using to describe it but simply some of the details were hidden in the "simple method" by the compiler]
>
>
> So, once you have such a type system. The way to deal with the complex relationships that exist are to know them:
>
> 1. A RCT have the following relationships between it's containing types. We will denote T to be a non-RCT type, FRCT to be an FRCT, and RCT to be an RCT.
>
>      RCT can contain T's, FRCT's, and/or, RCT's.
>
>      In Code:
>
>      rcclass RCT
>      {
>          T t;
>          FRCT myFRCT;
>          RCT myRCT;
>      }
>
>
> In this case, which is the only case we will talk about w.l.o.g), when an RCT is released it must attempt to release each of it's references... in example above: t, myFRCT, and myRCT. Since t is a simple type, it can be released immediately. No RCT's point to it because if they did, then T would be an RCT and it isn't. Similarly myFRCT can easily be released because it is just a complex of things like T's. In this case though there is something slightly different about it which is the referencing counting part. Essentially it's contained types are simple types but it still has a reference counting aspect for itself.
>
>
> Basically T's and FRCT's can free themselves when they need to. This is because they know how to free each reference they contain and it can't cause referential problems simply because they do not contain such references. This by no means they won't cause other parts of code to access invalid references. A pointer to such a member of a class can easily try and access the member after the object has been freed. But this is not our concern because we are only dealing with RCT's. Our goal isn't to have everything be RCT's. If that was the case then the T and FRCT cases would not be needed since we won't use them. e.g., We might want the GC to handle non-RCT and some other method for FRCT's. This allows one to build on current D system. But one must remember that RCT's only guarantee valid referencing when they access other RCT's.
>
>
> The last sentence above directs where we are going with this: Since we have RCT we can make sure they know how to communicate with each other. (we are creating a metatype here)
>
> By having the proper communication system here it is possible for the types to know when they need to be released.
> In fact, it is not hard and several methods can be used, even simultaneously.
>
> Axiom: Every RCT has the ability to have any other RCT that contains a reference to it, to be able to release it. Also, vice versa!
>
> [This requirement essentially allows the very final reference to know that it needs to release other dependencies it had and allows it to not only clean up itself but everything else it needs to clean up]
>
> Once you have the above requirement of RCT's(The implement dealt with at a different time), you can lazily release objects in the background without issue(fragmentation of the heap is a harder matter but still has a solution because of the above requirement).
>
> How do they communicate:
>
> Your example will do:
>
>     rcstruct T
>     {
>         void doSomething();
>     }
>
>     rcstruct S
>     {
>         T[] array;
>     }
>
>     void main()
>     {
>         auto s = S(new T());  // Here when the compiler creates the array of T's S knows T is a RFC.
>                               // In this case it can get at the hidden communications layer of T and
>                               // inform T that it is using it. Hence at this point
>                               // Both S and T can communicate with each other! (not just blind inc/dec of an int
>         auto t = s.array[0];
>
>         foo(s, s.array[0]);   // nothing special except foo much create an added reference to the two argments
>                               // This can be optimized out as long as foo returns once for every time it
>                               // is called. In this case, At the start of foo, the counters will be inc'ed
>                               // and at the end they will be dec'ed. Always a zero sum outside the function call.
>         t.doSomething();      // Skip to foo, come back when done with foo! Great, t is still around!
>                               // (RC is still zero at this point!)
>     }
>
>     void foo(ref S s, ref T t)
>     {
>         s.array = new T[];    // Here we are reassigning the array. No problem! We simply inc the ref count on the new array and decment it on the old. Just like normal ARC'ing! The only different is that t is not immediately release! Even though it has a RC count of 0. Think of it as lazy ARC'ing... or LARC'ing! ;)
>         t.doSomething();      // Great, even though t has an RC count of zero, it hasn't been released yet!
>     }
>
>
>
> So, what is this LARCING?
>
> Essentially instead of s simply dumping t in foo, it informs t that it is no longer using it. This sets the RC = 0 !!BUT!! t does not free itself immediately! If it does, it leads to the problem you have given and also to the extended problem I have shown above(calling t.doSomething in main).
>
>
> If t sticks around though, we are not releasing memory and hence what is the point?
>
>
> Well, as usual this is an engineering problem. We have a few cases.
>
>
> 1. The compiler can prove that a RCT goes out of scope and is not used any more. In this case t can release itself at the end of the function where it is provable that it is no longer used. (In your example it is at the end of foo ad in my example it is at the end of main) Flow analysis, simple brute force checking, etc are used here. Most cases in program will fall under this category. Local variables that are not referenced to by global variables are proven to be releasable at the end of the function call. Hence, many cases will work as simple ARC'ing and not require LARC'ing.
>
>
> 2. The compiler cannot prove when a variable is release. This is when the type itself has to decide when it is not being used. (this the last part of the problem and your example falls under it)
>
>
> In this case, the communication between S and T is crucial. When s decides it no longer need t, it informs t. t has a list of every reference that is using it(this can just be a pointer to the ref
> count of the RCT). Having this list, while potentially weighty, lets t know when all the references to it are not needed any more(sort of chains or links between any other RCT and t have been broken).
>
>
> Once this is done it is a simple matter of t trying to release itself every time it goes out of scope.
>
>      a. At some point t will release itself
>      b. t will never be able to release itself(this is generally due to program error in which a reference was made to t without removing the reference when it was done). Note this is why if every type is an RCT, prevents dangling(e.g., we would have full LARC'ing... or FLARC'ing.). FLARC'ing may not be optimal though(all pointers would have to be RCT which would probably be quiet inefficient. Also interdependencies are handled easily:
>
>
>          s.t = t;
> 		 t.s = s;
>          while (!isFree(t) && !isFree(s))
>          {
> 		     s.t = null;
> 			 t.s = null;
>              if (t.refCount == 0)
>                 s.release();
>              if (s.refCount == 0)
>                 t.release();
>
>          }
>
>          The reason that t and s are released in LARC'ing is because at the 2nd time through the loop s.release() knows that t no longer depend and can release itself immediately(because t.s = null set s's *t entry* to 0 on it so now s knows that t doesn't depend on it). This is just a prototype that can be used to show that any level of nesting between types will eventually resolve all releases properly.
> 		
>      c. Alternatively, a GC like memory manager can scan through the types and release all types who's reference count = 0 and who's dependencies are all invalid(nothing depends on it). It can do this in the background without issue and can compact consecutively release objects without issue. i.e., the GC knows what part of the heap belonged to objects there were ref counted and if it is proven they have any references then it can mark them as free'ed memory. Consecutive free'ed objects in memory can be combined since they never will be used again. This can be done behind in parallel and is sort of minor defragmentation. In fact, analogous to defragmenting a drive. If you know a file is not being used then you can defragment it in the background and move the various parts around without issue because you know it is not being used. Once it is being uses, you run into issues with having to stop the threads that are using that part of the heap. (I think this limitation could ultimately be removed for most practical cases.)
> 	
> 	 In this case the GC would have to have a list of all objects of RCT's. Essentially the GC is given to the task of LARC'ing in the background.
> 	
>
> 	
> Finally, which such an structural approach(Essentially implementing the reference list, which is a random access list containing all the references(pointers to all classes that use the type))  to ref counting becomes pretty stable and in probably 99%+ of program usage, statically proven to release memory(step a above, The compiler inserts many static releases that are released immediately and many types will be simple types that don't need LARC'ing).
>
>
> The two issues with this, as always, are speed and memory usage. I think it should rather fast(most releases are direct and just release themselves since they don't have references. On top of that the remaining are mostly FRCT's which can be released nearly immediately(they can, but don't until they are informed it is ok).
>
>
> For the full blown RCT types, the way they release things is in a hierarchical manner which can create avalanches of changes. If many objects are waiting for one object to be released, then when it does, they all could be released immediately. But this chain reaction is simply lazily recursive and eventually terminates.
>
>
> The only real problem is how to deal with un-managed references to RCT types. These are references(say pointers) to RCT's that may not be "smart"(inform the RFC that it is no longer being refered to. A simple pointer to a class that doesn't do any communication is the prototypical problem.
>
>
> The only solution seems to be to just accept it. It is a necessary evil. Allow it but require the program to know the intricate details. Such pointers are needed for speed and don't inherently cause any problems. It's only when they are abused can issues creep in.
>
>
> If one, say, had RCT pointers that are used for some types of problems and simple pointers when they are needed, it becomes pretty marginal of an issue. (if you are doing driver programming and have to have speed and direct access then use the simple pointers but it is your just to know if your references are working as expected.
>
>
> In many cases, RCT pointers can be used in many of the cases which make further minimize the singular problem case(that of non-informative referencing). (We could call such types "Peeping Toms"... but as long as they only peek it is ok(not by law, in programming ;)).
>
>
> At this, imagine that such a system was implemented. It would provide almost complete automatic memory management coverage with releasing resources as they are generally released in the program flow. In fact, with a GC(don't you just hate it when your garbage man doesn't pick up your trash sometimes? specially if he never picks it up) that essentially works parallel, most of the actual releasing can be done in the background without ever stopping the program. The benefits are: Better real-time behavior, Some programs might never need to compact the heap(in fact, if intelligent heap allocation is used, probably most programs could benefit from it), and debugging is much easier(Essentially more like manual management for most objects... just the compiler handles for us, but we know when, most likely, an object goes out of scope it will be released). Seg faults due to invalid memory access will almost be reduced to 0(since the corner case... the problem case of simple references is not used as much as all the other ways to use objects).
>
>
> The downside? There really isn't one except memory usage! One can come up with special cases that simply don't work well under LARC'ing but because it allows one to use non-LARC'ing types, the programmer will just have to manage it on is own or a mixed combination.
>
>
> Another great benefit is performance. One may think with all the all the extra allocation and deallocation code that the end's of functions would be slowed down(do to objects being lazily released). This is not necessarily the case because it is LARC'ing, the releases can be done later... say outside a performant piece of the code. It can even be faster than directly releasing it because that could be slow in and of itself, which, again, with LARC'ing, we can chose a better time to release the object or do it in the background.
>
>
> Unfortunately, if I'm not mistaken, with FLARC'ing, all classes would essentially double in size. This is because if every reference the type has is a RCT then it would essentially need to store a pointer to the object as to provide a link to it. With limited LARC'ing I think one could probably achieve a good balance. (for large classes and/or a large number of objects, one could just avoid LARC'ing to prevent the overhead and doing it manually or with GC)
>
> Some codetalk(tm) of how the interaction goes:
>
>      Object s is being initialized. It is a RFC type. It has, as a member, a object x that is also a RFC type.  In the course of s being initialized, it initializes x. We'll assume it is not null.
> 	 To do this s creates the object for x then informs x that it has a reference to it(we could have multiple types of references for further optimization if we want). e.g.,
> 	
> 	     x = new X;
> 	     x.CreateReference(s);
> 		 s.CreateReferenec(x); // We use directionless binding references
> 		
> 		
>     Now, suppose at some point s is being released. At the end of scope the compiler inserts
> 	
> 	     s.Release();
> 		
>     S now tries to release itself. It checks it's ref count and the list of all references it has.
> 	
> 	     e.g.,
> 		 refCount = 0;
> 		 refList = {}
> 		
> 		 then in s.Release()
> 		
> 			if (s.refCount == 0 && s.refList.IsEmpty)
> 			{
> 				GC.RemoveRCT(s); // GC.RemoveRCT is not necessary needed but using it hear for expressive purposes.
> 				s.Free();
> 			}
> 			else
> 				GC.AddRCT(s);   // Here, since the compiler potentially isn't going insert another s.Release() outside the function we have to let the GC handle it
> 			
> 		 in this case s free's itself immediately.
> 		
> 		 If either refCount != 0 or refList != empty, the GC is given control(it is made aware that S needs to be periodically checked to see if it can be released.(the GC simply does the
> 		 if (s.refCount == 0 && s.refList.IsEmpty) s.Free(); in a parallel thread. If s.refCount == 0 and s.refList is empty at some point then the GC ends up free'ing s.
> 		
> 		 Also, the compiler may be able to insert another s.Release() in the outer scope of the function all if it releases that it s was probably not released before. This doesn't hurt anything except an extra check that might be wasted(profiling could remove this check or even insert it).
> 		
> 		
> 		 The only way s can't be released is if it's refCount and refList are not empty. This is "danling" references and can only happen when mixing non-RCT's with RCT's.
> 		
> 		 So we know how s should release it self but how does t know that s no longer needs it? (so t can release itself at some point)
> 		
> 		 well, this has to do when x is assigned to. e.g.,
> 		
> 		 s.x = new X;
> 		 // Hidden, we have s update it's ref list and inform both the hold x and the new x what is going on.
> 		
> 		 here the assignment will need to remove the old x from refList and add the new x. This keeps the the list up to date. (there is a big corner case here that I believe would never occur but will have to think about it more)
> 		
> 		
> 		
> Any ways, I'll leave it at that for now!

tldr; ``I don't know what I'm talking about.``
Forums
