RCArray is unsafe

Biker via Digitalmars-d digitalmars-d at puremagic.com
Tue Mar 3 11:50:09 PST 2015


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.``


More information about the Digitalmars-d mailing list