www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Two suggestions for safe refcounting

reply "Zach the Mystic" <reachzach gggmail.com> writes:
As per deadalnix's request, a summary of my thoughts regarding 
the thread "RCArray is unsafe":

It's rather easy to guarantee memory safety from the safe 
confines of a garbage collected system. Let's take this as a 
given.

It's much harder when you step outside that system and try to 
figure out when it is or isn't safe to delete memory. It 
shouldn't be too surprising, therefore, that there are lots of 
pitfalls. Reference counting is a lonely outpost in the 
wilderness which is otherwise occupied by manual memory 
management. It's the only alternative to chaos.

But the walls protecting this outpost are easily breached by any 
dangling reference which is not accounted for.

We have seen two instances of how this can occur. The first, when 
boiled down to its essence, is that there is no corresponding 
bump in the reference count for a parameter which can alias an 
existing reference:

void fun(ref RCStruct a, ref RCStruct b);
RCStruct c;
fun(c,c); // c aliases itself

void gun(ref RCStruct a);
static RCStruct d;
gun(d); // d aliases global d

Because the workarounds are easy:
{
   RCStruct c;
   auto tmp = c;
   fun(c,tmp);

   auto tmp2 = d;
   gun(tmp2);
}
...it seems okay to mark these rare violations  system.

The second, harder problem, is when you take a reference to a 
subcomponent of an RC'd type, e.g. an individual E of an RCArray 
of E:

struct RCArray(E) {
   E[] array;
   int* count;
   ...
}
auto x =  RCArray([E()]);
E* t = &x[0];

Here's the problem. If x is assigned to a different RCArray, the 
one t points to will be deleted. On the other hand, if some 
special logic allows the definition of t to increment the 
reference count, then you have a memory leak, because t is not 
designed to keep track of x's original counter.

I don't know if we can get out of this mess. My suggestion 
represents a best-effort attempt. The only way I can see out of 
this problem is to redesign RCArray.

The problem with RCArray is that it "owns" the data it 
references. If a type different from RCArray, i.e. an individual 
E* into the array of E[], tries to reference the data, it's 
stuck, because it's not an RCArray!E. Therefore, you need to 
separate out the core data from the different types that can 
point to it. The natural place would be right next to its 
reference counter, in a separate struct:

struct RCData {
   int count = 0;
   void[] chunk;

   this(size_t size) {
     chunk = new void[size];
   }
   void addRef() {
     ++count;
   }
   void decRef() {
     if (--count == 0)
       delete chunk;
   }
}

Now RCArray can be redesigned to point to an RCData type. All new 
RC types will also contain a pointer to an RCData instance:

struct RCArray(E) {
   E[] array;
   private RCData* data;

   this(E[] a) {
     data = new RCData(a * sizeof(a));
     data.chunk = cast(void[]) a;
     array = a;
   }

   this(this) {
     data.addRef();
   }

   ~this() {
     data.decRef();
   }

   ref RCElement!E opIndex(size_t i) return {
     return RCElement!E(array[i], data);
   }
   ...
}

Note how the last member, opIndex, doesn't return a raw E*, but 
only an E* which is paired with a pointer to the same RCData 
instance as the RCArray is:

struct RCElement(E) {
   E* element;
   private RCData* data;

   this(this) {
     data.addRef();
   }
   ~this() {
     data.decRef();
   }
}

This is the best I could do.
Mar 05 2015
next sibling parent reply "Volodymyr" <iackhtak gmail.com> writes:
On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:
...

 Note how the last member, opIndex, doesn't return a raw E*, but 
 only an E* which is paired with a pointer to the same RCData 
 instance as the RCArray is:

 struct RCElement(E) {
   E* element;
   private RCData* data;

   this(this) {
     data.addRef();
   }
   ~this() {
     data.decRef();
   }
 }

 This is the best I could do.


It's needed to change type of this from RCArray to 
tuple!(RCArray, RCData). But as for me better to use Array and 
cahnge typeof(this) to RefCounter!Array:
assert(typeid(typeof(this)) == typeid(RefCounter!Array));

So how to deal with it:
struct RefCounter(T) // this is struct!
{
void opAddRef();
void opRelease();
alias this = __data;
void[] allocate(size_t)

// Hendler for sharing owned resources
auto opShareRes(MemberType)(ref MemberType field)
{
     return makeRefCounter(field, __count);
}

private:
size_t __count;
T __data;
}

 resource_owner(RefCounter)
class Array
{
ref int opIndex(size_t i) return
{
     return _data[i];
}

//// opIndex will be replaced with this function
//RefCounter!int opIndex(size_t i) //  return?
//{
//    assert(typeid(this) == typeid(RefCounter!Array));
//    return this.opShareResource(_data[i]);
//    // after inlining: return makeRefCounter(_data[i], __count);
//}

private int[] _data;
}

Method opShareRes is to move resources away(share with other 
owner) and an  return method will change its return type to 
opSharedRes return type. opShareRes also wraps access to public 
fields(and may change type of result).

Now Array is actualy alias to RefCounter!Array. Array creation is 
special case. "new Array" have to use RefCounter!Array.allocate. 
So owner manage array parts sharing, allocation and removing.

Options for  resource_owner
 resource_owner(this) - class provides 
opAddRef/opRelease/opShareRes by itself as in DIP74
 resource_owner(this, MyRCMixin) - MyRCMixin provides 
opAddRef/opRelease/opShareRes and will be mixed in class.(What 
DIP74 has in mind)
 resource_owner(Owner) - Owner is a template. Whenever you use 
owned type T it will be replaced with Owner!T(even type of 
"this"). This case prohibits changing owning strategy.

Resourse owning is close to memory management. Maybe resource 
owner have to set memory allocation strategy instead of providing 
method allocate.
Mar 06 2015
parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
On Friday, 6 March 2015 at 14:40:31 UTC, Volodymyr wrote:

 On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:
 ...

 Note how the last member, opIndex, doesn't return a raw E*, 
 but only an E* which is paired with a pointer to the same 
 RCData instance as the RCArray is:

 struct RCElement(E) {
  E* element;
  private RCData* data;

  this(this) {
    data.addRef();
  }
  ~this() {
    data.decRef();
  }
 }

 This is the best I could do.


 It's needed to change type of this from RCArray to 
 tuple!(RCArray, RCData). But as for me better to use Array and 
 cahnge typeof(this) to RefCounter!Array:
 assert(typeid(typeof(this)) == typeid(RefCounter!Array));

 So how to deal with it:
 struct RefCounter(T) // this is struct!
 {
 void opAddRef();
 void opRelease();
 alias this = __data;
 void[] allocate(size_t)

 // Hendler for sharing owned resources
 auto opShareRes(MemberType)(ref MemberType field)
 {
     return makeRefCounter(field, __count);
 }

 private:
 size_t __count;
 T __data;
 }

  resource_owner(RefCounter)
 class Array
 {
 ref int opIndex(size_t i) return
 {
     return _data[i];
 }

 //// opIndex will be replaced with this function
 //RefCounter!int opIndex(size_t i) //  return?
 //{
 //    assert(typeid(this) == typeid(RefCounter!Array));
 //    return this.opShareResource(_data[i]);
 //    // after inlining: return makeRefCounter(_data[i], 
 __count);
 //}

 private int[] _data;
 }

 Method opShareRes is to move resources away(share with other 
 owner) and an  return method will change its return type to 
 opSharedRes return type. opShareRes also wraps access to public 
 fields(and may change type of result).

 Now Array is actualy alias to RefCounter!Array. Array creation 
 is special case. "new Array" have to use 
 RefCounter!Array.allocate. So owner manage array parts sharing, 
 allocation and removing.

 Options for  resource_owner
  resource_owner(this) - class provides 
 opAddRef/opRelease/opShareRes by itself as in DIP74
  resource_owner(this, MyRCMixin) - MyRCMixin provides 
 opAddRef/opRelease/opShareRes and will be mixed in class.(What 
 DIP74 has in mind)
  resource_owner(Owner) - Owner is a template. Whenever you use 
 owned type T it will be replaced with Owner!T(even type of 
 "this"). This case prohibits changing owning strategy.


You've packed a lot of ideas into one post. Your solution might 
work, but it's hard for me to tell.


 Resourse owning is close to memory management. Maybe resource 
 owner have to set memory allocation strategy instead of 
 providing method allocate.


This is an open question. I'm still wrestling with understanding 
all the interlocking systems. The only reason I keep exploring 
them is that sometimes it seems like nobody else understands them 
either. ^_^
Mar 06 2015
parent "Volodymyr" <iackhtak gmail.com> writes:
On Friday, 6 March 2015 at 22:41:16 UTC, Zach the Mystic wrote:


 You've packed a lot of ideas into one post. Your solution might 
 work, but it's hard for me to tell.


Yeah... How about this one:
In C++ type of "this" is T*. If we could pass shared_ptr<T> as
"this" (instead of raw ptr) system will be much safer. Same
solution may be applied for D's "this" with RefCounter!T
Mar 10 2015
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 6 March 2015 at 07:46:13 UTC, Zach the Mystic wrote:

 The second, harder problem, is when you take a reference to a 
 subcomponent of an RC'd type, e.g. an individual E of an 
 RCArray of E:

 struct RCArray(E) {
   E[] array;
   int* count;
   ...
 }
 auto x =  RCArray([E()]);
 E* t = &x[0];


But taking that address is unsafe to begim with. Do arguably, 
this isn't that big of a problem.

Your first dual reference issue seems much more problematic, as 
there are always cases the compiler can't catch.
Mar 06 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Friday, 6 March 2015 at 14:59:46 UTC, monarch_dodra wrote:

 struct RCArray(E) {
  E[] array;
  int* count;
  ...
 }
 auto x =  RCArray([E()]);
 E* t = &x[0];


 But taking that address is unsafe to begin with. Do arguably, 
 this isn't that big of a problem.


Taking the address is only really unsafe (in a non-RC'd type) if 
you don't have a lifetime tracking system. As long as the 
lifetime of the address taker is shorter than the address of the 
takee, it's not inherently unsafe. Whether D will end up with 
such a system is a different question.

But I still think there's value in having a separate RCData type, 
because you can save one pointer per instance of RCArray. Right 
now, if you take a slice of an RCArray, your working array might 
not start at the same place as the reserved memory array. 
Therefore you need to keep a pointer to the reserved memory in 
addition to your active working array. If the counter and the 
pointer to the original memory are in the same place, one pointer 
will get you both.

I think the idea is worth exploring.


 Your first dual reference issue seems much more problematic, as 
 there are always cases the compiler can't catch.


How so? If all we're talking about is RC'd types, the compiler 
can catch everything. I think the greater concern is that the 
workarounds will take a toll in runtime performance. I'll try to 
illustrate:

void fun(ref RCStruct a, ref RCStruct b);

auto x = new RCStruct;
fun(x, x);

This wouldn't be safe. If fun() contained a line "a = new 
RCStruct;", b will point to deleted memory for the rest of the 
function. The normal way to protect this to make sure there's 
another reference:

auto y = x;
fun(x,x);

This is actually safe, because y bumps the reference counter to 2 
when initialized, which is enough to cover all possible 
reassignments of x. The compiler could do this automatically. It 
could detect that the parameter x aliases itself and create a 
temporary copy of x. But it would mean the runtime performance 
cost of the copy and postblit and destructor call. So D probably 
can't invest in that strategy, since the programmer should have a 
choice about it.

So it's not about it being impossible to deal with the safety 
problems here, just that the runtime cost is too high.

But there are some ways out. If the given type has no postblit, 
for example (or "opAddRef" for  classes), there's no reason to 
mark the operation unsafe, since you know it's not reference 
counted. Also, const parameters are safe and won't be affected.
Mar 06 2015