Реалізація reference counting або життя без GC (майже)

Доброго часу доби, хабр!

Багато хто вважає, що системний мову і збирач сміття — не сумісні поняття. У деяких ситуаціях, дійсно, збирач може доставляти деякі проблеми.

Як Вам, швидше за все, невідомо — D збирач сміття, почасти, опційний. Але ручне управління пам'яттю це минуле століття.
Тому сьогодні я покажу як можна реалізувати збірку сміття самому через «напівавтоматичний» підрахунок посилань, а так само як при цьому мінімізувати звернення до вбудованого в runtime збирача сміття на основі сканування пам'яті.



Вирішувати ми будемо завдання підрахунку посилань на покажчики, класи та масиви.
Відразу слід обговорити 2 моменти: чому від GC у цій статті ми не будемо відмовлятися і чому підрахунок посилань «напівавтоматичний».
Повна відмова від GC передбачає використання атрибуту @nogc для всього коду, але тут є одне АЛЕ. Інтерфейс
IAllocator
, який ми будемо використовувати, дозволяє створювати і знищувати екземпляри класу правильно однією командою (правильно це з викликом всіх конструкторів і все деструкторів ієрархії класів), а функції, які це роблять не помічені як @nogc і щоб не роздувати статтю ми не будемо їх реалізовувати самостійно (почасти в минулій статті це було рассмотренно).
Підрахунок посилань буде «інсолар», так як на даному етапі розвитку мови не можна виконати автоматично якийсь код при передачі або присвоєння ссылочних типів (класи і масиви), тому цей код буде викликати самі, але постараємося зробити це максимально приховано.

Почнемо з реалізації allocator'а.
static this() { RC.affixObj = allocatorObject(RC.affix); } // обертаємо в об'єкт

struct RC
{
static:
alias affix = AffixAllocator!(Mallocator,size_t,size_t).instance; // про це нижче
IAllocator affixObj;

// при створенні інкрементуємо лічильник
auto make(T,A...)( auto ref A args )
{ return incRef( affixObj.make!T(args) ); }

// безпосередньо ми не можемо вивільнити об'єкт, тільки через зменшення лічильника
private void dispose(T)( T* p ) { affixObj.dispose(p); }

private void dispose(T)( T p )
if( is(T == class) || is(T == interface) )
{ affixObj.dispose(p); }

// affix.prefix( void[] p ), де p-область виділеної пам'яті,
// а не просто вказівник на неї, тому виглядає так негарно
ref size_t refCount(T)( T p )
if( is(T == class) || is(T == interface) )
{ return affix.prefix( (cast(void*)p)[0..__traits(classInstanceSize,T)] ); }

ref size_t refCount(T)( T* p )
{ return affix.prefix( (cast(void*)p)[0..T. sizeof] ); }

// збільшення лічильника, повертаємо об'єкт для зручності
auto incRef(T)( auto ref T p )
{
if( p is null ) return null;
refCount(p)++;
return p;
}

// зменшення лічильника, повертаємо об'єкт для зручності, null якщо лічильник дорівнює 0
auto decRef(T)( T p )
{
if( p is null ) return null;
if( refCount(p) > 0 )
{
refCount(p)--;
if( refCount(p) == 0 )
{
dispose(p); 
return null;
}
}
return p;
}
}

В основі нашого аллокатора лежить
Mallocator
— аллокатор, що працює через C-шні
malloc
та
free
. Ми обернули його в
AffixAllocator
. Він параметризируется використовуваним справжнім аллокатором і 2-ма типами даних. При виділенні пам'яті
AffixAllocator
выделяеть трохи більше: розмір
Prefix
та
Suffix
типів (відповідно другий і третій параметр шаблонізації). Як можна здогадатися префікс знаходиться до виділеної під об'єкт пам'яті, а суфікс-після. У нашому випадку
Prefix
та
Suffix
size_t
, і як раз префікс у нас і буде уособлювати лічильник посилань.
Такий підхід дозволяє без модифікації використовувати вже існуючі класи, так як інформація про кількість посилань зберігається поза об'єкта.

Тепер ми можемо створювати і знищувати об'єкти класів і покажчики з допомогою нашого аллокатора.
auto p = RC.make!int( 10 );
assert( is( typeof(p) == int* ) );
assert( *p = 10 );
assert( RC.refCount(p) == 1 );
p = RC.decRef(p);
assert( p is null );

Вже щось, але поки не цікаво: тільки make за нас инкрементирует лічильник, далі інкрементуємо і декриментируем ми його самостійно.

Додамо обгортку, яка буде деякі речі робити за нас.
struct RCObject(T)
{
T obj;
alias obj this; // де буде потрібно, компілятор просто підставить obj поле замість самого об'єкта RCObject

this(this) { incRef(); } // конструктор копіювання -- збільшуємо лічильник

this( T o ) { obj = o; incRef(); } // створюється нова обгортка -- збільшуємо лічильник

// повинна бути можливість помістити об'єкт у обгортку без зміни лічильника посилань (коли він приходить відразу з RC.make)
package static auto make( T o )
{
RCObject!T ret;
ret.obj = o;
return ret;
}

// nothrow тому що цього вимагає деинциализатор з std.experimental.allocator
~this() nothrow
{
if( obj is null ) return;
try decRef();
catch(Exception e)
{
import std.experimental.logger;
try errorf( "ERROR: ", e );
catch(Exception e) {}
}
}

void incRef()
{
if( obj is null ) return;
RC.incRef(obj);
}

/// видалить obj якщо крім цього посилання більше немає ні однієї
void decRef()
{ 
if( obj is null ) return;
assert( refCount > 0, "not null object have 0 refs" );
obj = RC.decRef(obj);
}

size_t refCount() @property const
{
if( obj is null ) return 0;
return RC.refCount(obj);
}

// при присвоєнні для старого об'єкта зменшується кількість посилань, а після присвоєння нового додається
void opAssign(X=this)( auto ref RCObject!T r )
{
decRef();
obj = r.obj;
incRef();
}

/// теж саме тільки робота з голим типом T, без обгортки
void opAssign(X=this)( auto ref T r )
{
decRef();
obj = r;
incRef();
}
}

// для зручності
auto rcMake(T,A...)( A args ){ return RCObject!(T).make( RC.make!T(args) ); }

Тепер у нас є scope-залежний підрахунок посилань і ми можемо робити так:
static class Ch { }

{
RCObject!Ch c;
{
auto a = rcMake!Ch();
assert( a.refCount == 1 );
auto b = a;
assert( a.refCount == 2 );
assert( b.refCount == 2 );
c = a;
assert( a.refCount == 3 );
assert( b.refCount == 3 );
assert( c.refCount == 3 );
b = rcMake!Ch();
assert( a.refCount == 2 );
assert( b.refCount == 1 );
assert( c.refCount == 2 );
b = rcMake!Ch(); // тут старий об'єкт віддаляється, а новий запишеться
assert( a.refCount == 2 );
assert( b.refCount == 1 );
assert( c.refCount == 2 );
}
assert( c.refCount == 1 );
}

Це вже щось! Але як же бути з масивами? Додамо роботу з масивами в наш аллокатор:
...
T[] makeArray(T,A...)( size_t length )
{ return incRef( affixObj.makeArray!T(length) ); }

T[] makeArray(T,A...)( size_t length, auto ref T init )
{ return incRef( affixObj.makeArray!T(length,init) ); }

private void dispose(T)( T[] arr ) { affixObj.dispose(arr); }

ref size_t refCount(T)( T[] arr ) { return affix.prefix( cast(void[])arr ); }
...

І реалізуємо обгортку для масивів.
вона мало відрізняється від обгортки для об'єктів
struct RCArray(T)
{
// вважаємо посилання на пам'ять, яку виділили
private T[] orig;
// а можемо працювати зі зрізом
T[] work;

private void init( T[] origin, T[] slice )
{
if( slice !is null )
assert( slice.ptr >= origin.ptr &&
slice.ptr < origin.ptr + origin.length,
"slice is not in original" );

orig = origin;
incRef();

work = slice is null ? orig : slice;

static if( isRCType!T ) // якщо елементи є обгортками
foreach( ref w; work ) w.incRef; // додаємо лічильник тільки робочого набору
}

///
alias this work;

this(this) { incRef(); } конструктор копіювання

this( T[] orig, T[] slice=null ) { init( orig, slice ); }

/// no increment ref
package static auto make( T[] o )
{
RCArray!T ret;
ret.orig = o;
ret.work = o;
return ret;
}

// зріз повертає обгортку
auto opSlice( size_t i, size_t j )
{ return RCArray!T( orig, work[i..j] ); }

void opAssign(X=this)( auto ref RCArray!T arr )
{
decRef();
init( arr.orig, arr.work );
}

void incRef()
{
if( orig is null ) return;
RC.incRef(orig);
}

void decRef()
{
if( orig is null ) return;
assert( refCount > 0, "not null object have 0 refs" );
orig = RC.decRef(orig);
}

size_t refCount() @property const
{
if( orig is null ) return 0;
return RC.refCount(orig);
}

~this()
{
if( refCount )
{
// логічний хак
if( refCount == 1 )
{
static if( isRCType!T )
foreach( ref w; orig )
if( w.refCount )
w.incRef;
}

static if( isRCType!T ) // якщо елементи обгортки
foreach( ref w; work ) w.decRef;
decRef;
}
}
}

template isRCType(T)
{
static if( is( T E = RCObject!X, X ) || is( T E = RCArray!X, X ) )
enum isRCType = true;
else
enum isRCType = false;
}


але є деякі принципові моменти:
  1. в обгортці для масивів ми зберігаємо масив виділеної пам'яті і робочий зріз
  2. в конструкторі, якщо елементи є обгортками, збільшуємо для елементів робочого зрізу лічильник посилань
  3. деструкторе у цій же ситуації зменшуємо
Так само в деструкторе є невеликий логічний хак: припустимо у нас зберігся тільки фрагмент масиву, а обгортка на оригінальний масив канула в лету. Тоді виходить, що лічильник посилань
orig
дорівнює 1, це означає, що якщо серз теж буде видалений, то буде викликаний
dispose
для початкового (
orig
) масиву, це призведе до того, що об'єкти, узяті з оригінального масиву, але не потрапляють в зріз будуть піддані операції зменшення лічильника посилань та можуть бути видалені. Щоб це не сталося ми додаємо +1 кожного елемента, у якого вже є більше 1. Потім буде відбуватися зменшення у робочого набору, це дозволить залишити на 1 більше елементів вихідного масиву, які не увійшли в робочий набір і при удалии оригінального масиву їх лічильник не дійде до нуля.

Все це разом дозволяє робити нам ось такі речі:
class A
{
int no;
this( int i ) { no=i; }
}

alias RCA = RCObject!A;

{
RCA obj;
{
RCArray!RCA tmp1;
{
RCArray!RCA tmp2;
{
auto arr = rcMakeArray!RCA(6);
foreach( int i, ref a; arr )
a = rcMake!A(i);
assert( arr[0].refCount == 1 );
assert( arr[1].refCount == 1 );
assert( arr[2].refCount == 1 );
assert( arr[3].refCount == 1 );
assert( arr[4].refCount == 1 );
assert( arr[5].refCount == 1 );

tmp1 = arr[1..4];
assert( arr[0].refCount == 1 );
assert( arr[1].refCount == 2 );
assert( arr[2].refCount == 2 );
assert( arr[3].refCount == 2 );
assert( arr[4].refCount == 1 );
assert( arr[5].refCount == 1 );

tmp2 = arr[3..5];
assert( arr[0].refCount == 1 );
assert( arr[1].refCount == 2 );
assert( arr[2].refCount == 2 );
assert( arr[3].refCount == 3 );
assert( arr[4].refCount == 2 );
assert( arr[5].refCount == 1 );

obj = tmp2[0];
assert( arr[0].refCount == 1 );
assert( arr[1].refCount == 2 );
assert( arr[2].refCount == 2 );
assert( arr[3].refCount == 4 );
assert( arr[4].refCount == 2 );
assert( arr[5].refCount == 1 );
}
assert( tmp1[0].refCount == 1 );
assert( tmp1[1].refCount == 1 );
assert( tmp1[2].refCount == 3 );

assert( obj.refCount == 3 );

assert( tmp2[0].refCount == 3 );
assert( tmp2[0].obj.no == 3 );
assert( tmp2[1].refCount == 1 );
assert( tmp2[1].obj.no == 4 );
}
assert( tmp1[0].refCount == 1 );
assert( tmp1[1].refCount == 1 );
assert( tmp1[2].refCount == 2 );
assert( obj.refCount == 2 );
}
assert( obj.refCount == 1 );
}
// тут буде видалено останній елемент з індексом 3

Хоч код і не позначено як
@nogc
, він не звертається до вбудованому GC. А як ми знаємо не чіпай і не запахне не виділяй через GC і він не буде збирати.

На цьому все, сподіваюся, Ви щось нове для себе подчерпнули)

Код оформлений пакет dub.
Сорцы на github.

Це не готова бібліотека, а поки просто начерк, він вимагає ще багато доопрацювань.
Буду дуже радий допомозі, якщо не ділом, так радою.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.