Jump to page: 1 2
Thread overview
Enhancements can enable memory-safe reference counting
May 14
tsbockman
May 23
jmh530
May 25
Gavin Ray
May 25
tsbockman
May 26
vitoroak
May 26
tsbockman
May 26
tsbockman
May 27
vitoroak
May 27
tsbockman
May 27
vitoroak
May 27
tsbockman
May 27
IGotD-
May 28
tsbockman
May 14

I have written an experimental D reference counting system with a memory @safe API. It supports slices, classes, dynamic casts, and -betterC.

I found this task just barely possible today, with DIP25 / DIP1000 enabled (ignoring some bugs like 20150 "-dip1000 defeated by pure"). But, some of the techniques I used to do it are rather nasty hacks, and I'm sure no one would want my solution in the standard library.

However, there are some fairly simple language enhancements that would make it possible to remove most of the hacks:

The most important changes relate to scope and return (as in DIP25's return ref):

(0) return should apply consistently to all indirections, especially ref, *, [], and class, since these all use pointers under the hood.

(1) When calling a return annotated function, assigning the returned indirection should be considered valid or invalid based on whether the receiving indirection provably has a lifetime that is fully contained inside the lifetime of the return annotated input indirection(s) for the function.

(2) foreach and foreach_reverse should support scope.

Basically, annotating a function with return becomes a way to force callers to treat the return value as head scope, except when this can be proven unnecessary based on the lifetime of the relevant input(s).

A small example program (my real system is too large to embed in this message):

module app;

import core.stdc.stdlib : malloc, free;
import core.lifetime : emplace;

import std.traits;

struct Unique(_Address)
    if(is(Unqual!_Address : Target*, Target) || is(_Address == class))
{
    alias Address = _Address;
    private Address _address;
    Address address() return pure @safe {
        return _address; }
    alias address this;

    static if(is(Unqual!Address : Target*, Target)) {
        alias Access = Target;
        ref Access access() return pure @safe {
            return *_address; }
        alias Slice = Access[];
        Access[] slice() return pure @trusted {
            return _address[0 .. (_address !is null)]; }
    } else {
	static assert(is(Address == class));
        alias Access = Address;
        Access access() return pure @safe {
            return _address; }
        alias Slice = const(Access)[];
        Slice slice() return const pure @trusted {
            return (*cast(Access[1]*) &_address)
                [0 .. (_address !is null)];
        }
    }
    alias opUnary(string op : `*`) = access;
    alias opIndex() = slice;

    this(const(bool) value) @trusted {
        if(value) {
            static if(is(Access == Address)) {
                _address = cast(Address)
                	malloc(__traits(classInstanceSize, Access));
            } else {
        		_address = cast(Address)
                	malloc(Access.sizeof);
            }
            emplace(_address);
        } else
            _address = null;
    }
    @disable ref typeof(this) opAssign(ref typeof(this));
    @disable this(this);
    @disable this(ref typeof(this));
    ~this() @trusted {
        if(_address !is null) {
            destroy!false(access);
        	free(cast(void*) _address);
            _address = null;
        }
    }
}

void test(Address)() @safe {
    Unique!Address up = true;
    with(up) {
        static a = Address.init, c = Address.init, e = Slice.init;
        scope b = Address.init, d = Address.init, f = Slice.init;

        static if( __traits(compiles, a = up.address)) {
            pragma(msg, "a: ACCEPTS INVALID: static " ~ Address.stringof ~
                " = return " ~ Address.stringof);
        }
        static if(!__traits(compiles, b = up.address)) {
            pragma(msg, "d: REJECTS VALID: scope " ~ Address.stringof ~
				" = return " ~ Address.stringof);
        }
        static if(!is(Access == Address)) {
            static if( __traits(compiles, c = &(up.access))) {
                pragma(msg, "b: ACCEPTS INVALID: static " ~ Address.stringof ~
                	" = &(return ref " ~ Access.stringof ~ ")");
            }
            static if(!__traits(compiles, d = &(up.access))) {
                pragma(msg, "e: REJECTS VALID: scope " ~ Address.stringof ~
					" = &(return ref " ~ Access.stringof ~ ")");
            }
        }
        static if( __traits(compiles, e = up.slice)) {
            pragma(msg, "c: ACCEPTS INVALID: static " ~ Slice.stringof ~
				" = return " ~ Slice.stringof);
        }
        static if(!__traits(compiles, f = up.slice)) {
            pragma(msg, "f: REJECTS VALID: scope " ~ Slice.stringof ~
				" = return " ~ Slice.stringof);
        }

        static if(!is(Access == Address)) {
            static Access g, i, k;
            scope Access h, j, l;

            static if(!__traits(compiles, g = up.access)) {
                pragma(msg, "g: REJECTS VALID: static " ~ Access.stringof ~
					" = return ref " ~ Access.stringof);
            }
            static if(!__traits(compiles, h = up.access)) {
                pragma(msg, "j: REJECTS VALID: scope " ~ Access.stringof ~
					" = return ref " ~ Access.stringof);
            }
            static if(!__traits(compiles, i = *(up.address))) {
                pragma(msg, "h: REJECTS VALID: static " ~ Access.stringof ~
					" = *(return " ~ Address.stringof ~ ")");
            }
            static if(!__traits(compiles, j = *(up.address))) {
                pragma(msg, "k: REJECTS VALID: scope " ~ Access.stringof ~
					" = *(return " ~ Address.stringof ~ ")");
            }
            static if(!__traits(compiles, k = up.slice[0])) {
                pragma(msg, "i: REJECTS VALID: static " ~ Access.stringof ~
					" = (return " ~ Slice.stringof ~ ")[0]");
            }
            static if(!__traits(compiles, l = up.slice[0])) {
                pragma(msg, "l: REJECTS VALID: scope " ~ Access.stringof ~
					" = (return " ~ Slice.stringof ~ ")[0]");
            }
        }
    }
}

class D { }
void main() @safe {
    test!(int**)();
    test!D();
}

Output with -dip1000:

a: ACCEPTS INVALID: static int** = return int**
e: REJECTS VALID: scope int** = &(return ref int*)
c: ACCEPTS INVALID: static int*[] = return int*[]
a: ACCEPTS INVALID: static D = return D

(-dip1000 only prevented this one error, although I believe it does do some other good things that are not tested above):

c: ACCEPTS INVALID: static const(D)[] = return const(D)[]

Currently, in order to have a truly @safe API I must work around the above issues by marking various things @system that shouldn't need to be @system, and then offering awkward but safe borrowing with something like this:

mixin template borrow(alias owner, string name) {
    mixin(`scope `, name, ` = () @trusted { pragma(inline, true); return owner.address; }();`);
}

With my earlier proposed changes to return and scope, though, the borrow mixin would be unnecessary.

I think D is very close to being able to sanely express @safe reference counting APIs. I don't think @live is necessary; rather, we just need to complete scope and return and fix some RAII related bugs. For performance reasons, move operators and some minor changes to the GC would also be good, but are not actually required.

Destroy?

May 23

On Friday, 14 May 2021 at 00:45:09 UTC, tsbockman wrote:

>

[snip]

Destroy?

It's a bit of a shame that there aren't any other comments here because it seemed interesting, but I didn't have the time to really dig into this to understand everything going on.

May 23

On Friday, 14 May 2021 at 00:45:09 UTC, tsbockman wrote:

>

I have written an experimental D reference counting system with a memory @safe API. It supports slices, classes, dynamic casts, and -betterC.

[...]

This is interesting. I totally missed this post earlier ☀️

May 25

On Sunday, 23 May 2021 at 13:03:58 UTC, jmh530 wrote:

>

On Friday, 14 May 2021 at 00:45:09 UTC, tsbockman wrote:

>

[snip]

Destroy?

It's a bit of a shame that there aren't any other comments here because it seemed interesting, but I didn't have the time to really dig into this to understand everything going on.

Is there anyone smarter than myself that might be willing to explain/comment the code and what's going on here? Would be much appreciated =D

I think I understand that it's some sort of ownership/refcounting system that's meant to provide scope-based safe resource usage but I am not sure I can appreciate the brilliance to it's fullest.

May 25

On Tuesday, 25 May 2021 at 18:40:52 UTC, Gavin Ray wrote:

>

explain/comment the code and what's going on here? Would be much appreciated =D

What would you like explained? Or alternatively, which parts of the code do make sense to you?

A full explanation without making any assumptions about your background and experience, other than a minimal working knowledge of D, would be multiple pages long.

>

I think I understand that it's some sort of ownership/refcounting system that's meant to provide scope-based safe resource usage

That is the goal of the full system, yes. The code in my original post isn't intended for practical use, though. It's just a demonstration of some bugs or missing features in the current implementation of return, together with a small demonstration of the practical value of fixing them.

May 26

On Friday, 14 May 2021 at 00:45:09 UTC, tsbockman wrote:

>

[snip]

I think D is very close to being able to sanely express @safe reference counting APIs. I don't think @live is necessary; rather, we just need to complete scope and return and fix some RAII related bugs. For performance reasons, move operators and some minor changes to the GC would also be good, but are not actually required.

Destroy?

Every time I tried to do something similar in D I stumbled across the same problems and as far as I know it's not possible to implement it completely @safe today. I think one of the problems is that you can manually destroy/move any struct while there are still references/pointers to it or its internals like in the example below (I used your borrow mixin template).

void receiveByValue(Unique!(int*) u) @safe {
}

void main() @safe {
    import std.stdio: writeln;

	auto u1 = Unique!(int*)(true);
    mixin borrow!(u1, "x1");
    writeln(*x1); // ok
    destroy(u1);
    writeln(*x1); // should not be possible

    import core.lifetime: move;

    auto u2 = Unique!(int*)(true);
    mixin borrow!(u2, "x2");
    writeln(*x2); // ok
    receiveByValue(move(u2));
    writeln(*x2); // should not be possible
}

I don't know how this could be solved but for me it's a blocker to do a @safe Unique or RC type. Maybe if I always return an RCRef or something like this but I think the overhead would be too big.

May 26

On Wednesday, 26 May 2021 at 18:53:21 UTC, vitoroak wrote:

>

Every time I tried to do something similar in D I stumbled across the same problems and as far as I know it's not possible to implement it completely @safe today. I think one of the problems is that you can manually destroy/move any struct while there are still references/pointers to it or its internals like in the example below (I used your borrow mixin template).

void receiveByValue(Unique!(int*) u) @safe {
}

void main() @safe {
    import std.stdio: writeln;

	auto u1 = Unique!(int*)(true);
    mixin borrow!(u1, "x1");
    writeln(*x1); // ok
    destroy(u1);
    writeln(*x1); // should not be possible

Yes, that is a problem.

Manually calling destroy or __dtor really should be an @system operation, regardless of the attributes of __dtor itself. The whole point of destructors is to ensure that cleanup work is performed at the correct point, and potentially subverting that should not be considered @safe.

>
    import core.lifetime: move;

    auto u2 = Unique!(int*)(true);
    mixin borrow!(u2, "x2");
    writeln(*x2); // ok
    receiveByValue(move(u2));
    writeln(*x2); // should not be possible
}

That second test, with move, actually doesn't compile (although I'm not sure why):

onlineapp.d(150): Error: @safe function D main cannot call @system function core.lifetime.move!(Unique!(int*)).move
/dlang/dmd-nightly/linux/bin64/../../src/druntime/import/core/lifetime.d(1587):        core.lifetime.move!(Unique!(int*)).move is declared here
May 26

On Wednesday, 26 May 2021 at 18:53:21 UTC, vitoroak wrote:

>

Every time I tried to do something similar in D I stumbled across the same problems and as far as I know it's not possible to implement it completely @safe today. I think one of the problems is that you can manually destroy/move any struct while there are still references/pointers to it or its internals like in the example below (I used your borrow mixin template).

In theory, these examples are fine, since they result in a null dereference, which is guaranteed by the language spec to be memory-safe (i.e., to immediately crash the program).

In practice, this is usually what will happen, but neither DMD, LDC, nor GDC actually guarantees an immediate crash upon null dereference in all cases. In particular, a null dereference with a large enough offset (e.g., a struct or class member access through a null pointer) can in principle cause memory corruption at runtime by accessing an address beyond the protected pages at the start of the address space.

You can work around this by adding an explicit null check:

pure @safe
ref Access access() return
{
    // assert(0) is not compiled out in release mode
    if (_address !is null) assert(0);
    return *_address;
}
May 26

On Wednesday, 26 May 2021 at 21:48:40 UTC, Paul Backus wrote:

>

On Wednesday, 26 May 2021 at 18:53:21 UTC, vitoroak wrote:

>

Every time I tried to do something similar in D I stumbled across the same problems and as far as I know it's not possible to implement it completely @safe today. I think one of the problems is that you can manually destroy/move any struct while there are still references/pointers to it or its internals like in the example below (I used your borrow mixin template).

In theory, these examples are fine, since they result in a null dereference,

No. That's what I thought at first, too, but if you walk through the code more carefully you will see that x1 never gets set to null, and still points to the old target of u1. So, he is correct.

I've opened issue #21981 requesting a fix.

May 27

On Wednesday, 26 May 2021 at 22:06:27 UTC, tsbockman wrote:

>

On Wednesday, 26 May 2021 at 21:48:40 UTC, Paul Backus wrote:

>

On Wednesday, 26 May 2021 at 18:53:21 UTC, vitoroak wrote:

In theory, these examples are fine, since they result in a null dereference,

No. That's what I thought at first, too, but if you walk through the code more carefully you will see that x1 never gets set to null, and still points to the old target of u1. So, he is correct.

I've opened issue #21981 requesting a fix.

Thanks, I see the problem now.

I guess the conclusion we're forced to come to is that, given current language rules, it is incorrect to mark the destructor as @trusted.

« First   ‹ Prev
1 2