Часть 1

Содержание

Heap
Array
- adt и ref adt
GC
- Отключение объекта в heap от GC

Heap

Чтобы на C корректно создавать и уничтожать сложные структуры, с которыми будет работать код на Limbo, необходимо представлять себе как они хранятся в памяти, т.е. как организован heap в Inferno. Все упомянутые ниже функции для работы с heap описаны в libinterp/heap.c, а структуры в include/interp.h.

Что в памяти моей…

Для того, чтобы просто выделить n байт в heap, а потом их освободить, необходимо проделать следующее:

Heap *h;
uchar *data;

h = nheap(256);
data = H2D(uchar*, h);
... // работаем с data размером 256 байт
destroy(data);

Физически в памяти при этом будет выделено 256 + размер heap-заголовка байт, и в начале будет лежать заголовок, а потом пользовательские данные. Заголовок описан в структуре Heap, плюс есть два макроса для преобразования указателя на heap-заголовок в указатель на данные (причём для удобства сразу с приведением типа) H2D() и наоборот D2H(). Функция destroy() использует D2H() чтобы получить вместо указателя на начало пользовательских данных неизвестной длины их heap-заголовок и узнать, сколько же байт необходимо освободить.

struct Heap
{
        int     color;          /* Allocation color */
        ulong   ref;
        Type*   t;
        ulong   hprof;  /* heap profiling */
};

#define H2D(t, x)       ((t)(((uchar*)(x))+sizeof(Heap)))
#define D2H(x)          ((Heap*)(((uchar*)(x))-sizeof(Heap)))

Немного о сборке мусора

Что же находится в заголовке heap? Про hprof я вам ничего не скажу, с профайлингом heap я не разбирался, но остальные поля крайне важны.

Для начала пара слов о сборщике мусора в Inferno. Используются одновременно две стратегии: простой счётчик ссылок которого достаточно для большинства структур, плюс вариация на тему tri-colour marking для подбирания структур с цикличными ссылками. Соответственно, ref это счётчик ссылок, а color используется для tri-colour marking. Когда nheap() или другая аналогичная функция выделяет на heap новый объект, в его heap-заголовке значение ref устанавливается в 1. Когда вызывается destroy(), она уменьшает на 1 значение ref, и только если ref стал равен 0 — освобождает занятую этим объектом память.

Соответственно, пока вы храните значение возвращённое nheap() (или любой другой аналогичной функцией) в одной переменной — у вас ровно одна ссылка на этот объект, и его ref равен 1. Как только вы копируете эту ссылку в другую переменную — необходимо увеличить счётчик ссылок плюс уведомить об этом tri-colour алгоритм. Делается это так (Setmark() это тоже макрос, но чтобы с ним разобраться нужно понимать работу tri-colour алгоритма, что прямо сейчас от вас не требуется):

Heap *h;
uchar *data, *data2;

data = H2D(uchar*, nheap(256));

data2 = data;
h = D2H(data2);
h->ref++;
Setmark(h);     // работает с h->color

destroy(data);  // данные из памяти не будут удалены
destroy(data2); // а вот теперь будут удалены

Разумеется, если вы выделили объект в heap, а потом вернули его пользователю записав в *f->ret, то ничего дополнительно с ref и color делать не требуется — из локальных переменных вашей функции ссылка будет удалена при завершении функции, и снова останется только одна ссылка на этот объект — у пользователя, в переменной куда он сохранил возвращённое вашей функцией значение, т.е. произошло перемещение, а не копирование ссылки.

Есть один неявный нюанс связанный с перемещением ссылок. В предыдущем примере с возвращаемым значением происходит перемещение новой, только что созданной ссылки, и ничего дополнительного там не требуется. Но если вы переместили ссылку из одной уже существующей переменной/структуры в другую, тоже уже существующую, то необходимо уведомить об этом tri-colour алгоритм вызовом Setmark() (это тоже связано с особенностями работы этого алгоритма и будет описано ниже):

dst->data = src->data;
src->data = H;
Setmark(D2H(dst->data));

Типы объектов в heap

Описанный выше пример с nheap() в реальном коде практически никогда не используется, т.к. в Limbo нет такого типа данных: n байт. Поэтому ни получить из Limbo ни вернуть в Limbo выделенный через nheap() объект не получится. А для выделения памяти для внутренних нужд вашего C-модуля как правило хватает и обычных malloc() с free().

Все объекты в heap, с которыми может оперировать Limbo, должны относится к какому-нибудь типу, описанному структурой Type. Это позволяет решить задачу автоматического обнаружения всех ссылок внутри любого объекта — что необходимо проделать при:

выделении памяти под этот объект (чтобы установить все указатели внутри него в H a.k.a. nil);
выполнении destroy() (чтобы при удалении объекта из памяти вместе с ним удалить или уменьшить ref у всех объектов на которые он ссылался);
работе сборщика мусора (чтобы при обходе всех объектов в памяти учесть и объекты, ссылки на которые находятся внутри других сложных объектов).

struct Type
{
        int     ref; 
        void    (*free)(Heap*, int); 
        void    (*mark)(Type*, void*);
        int     size;
        int     np;
        void*   destroy;
        void*   initialize;
        uchar   map[STRUCTALIGN];
};

Для стандартных типов (любая adt/кортеж/структура, которая содержит либо не ссылочные поля, либо поля со ссылками на обычные heap-объекты которые можно освободить через destroy() — вроде String* и Array*) используются поля np и map. Поле map содержит битовую маску, по одному биту (начиная со старшего бита первого байта) на каждые 4 байта adt/кортежа/структуры, где установленный бит означает что соответствующие ему 4 байта это указатель на heap-объект. (Поле np содержит длину поля map в байтах.)

Некоторые типы данных используют память не совсем стандартным способом. Типичные примеры это String и Array — первый содержит внутри себя поле char*, которое требуется освобождать через free(); второй может быть срезом и содержать внутри себя ссылку на «родительский» массив. Структура Type позволяет указать для таких типов свои нестандартные функции-обработчики, которые будут вызываться при выделении/инициализации памяти, из destroy() и из сборщика мусора: free, mark, destroy и initialize.

Поле size содержит размер структуры этого типа (раз уж мы всё-равно вынуждены при выделении памяти под эту структуру указывать её тип, сохранение размера структуры внутри типа позволяет ограничиться указанием только типа, не добавляя к нему каждый раз ещё и размер структуры).

Поле ref используется для хранения текущего количества объектов в heap данного типа. Дело в том, что список типов не ограничен стандартными string, array of, etc. — любой описанный на лету кортеж это отдельный тип, для которого нужно своё описание структурой Type. Получается, что некоторые типы создаются Limbo на лету, хранятся в том же heap, и должны быть удалены из памяти как только удаляются все объекты этого типа. Поэтому при создании нового объекта некоторого типа, у этого типа необходимо увеличить ref, а при удалении этого объекта destroy() автоматически уменьшит ref так же и у типа этого объекта (и удалит его из памяти если ref станет равен 0).

Значения Type для стандартных типов объявлены статически, с ref выставленным в 1 (так что их ref никогда не станет меньше 1 и они никогда не будут удалены из памяти), и описаны в начале libinterp/head.c:

Type Tbyte   = { 1, 0,          0,         1              };
Type Tword   = { 1, 0,          0,         sizeof(WORD)   };
Type Tptr    = { 1, 0,          markheap,  sizeof(WORD*), 1, 0, 0, { 0x80 } };
Type Tarray  = { 1, freearray,  markarray, sizeof(Array)  };
Type Tstring = { 1, freestring, noptrs,    sizeof(String) };
...

Создаём свои сложные структуры в heap

Типы для ваших собственных adt/кортежей/структур в некоторых случаях поможет определить libinterp/runt.h (вычислив размер вашей структуры для Type.size и битовую маску полей-указателей для Type.map и Type.np), в других вам придётся определять их самостоятельно (например, чтобы создать и вернуть кортеж из C-функции). Создаются они обычно при инициализации вашего модуля (возвращаясь к примеру с модулем Example) с помощью функции dtype(). А выделяется и инициализируется для них память через heap(&Tsometype), а не nheap(n_bytes).

module/example.m

Example: module
{
        ...
        MyData: adt{
                i: int;
                s: string;
                new: fn(i: int): ref MyData;
        };
};

libinterp/runt.h (генерируется автоматически из module/example.m)

typedef struct Example_MyData Example_MyData;
struct Example_MyData
{
        WORD    i;
        String* s;
};
#define Example_MyData_size 8
#define Example_MyData_map {0x40,}

void MyData_new(void*);
typedef struct F_MyData_new F_MyData_new;
struct F_MyData_new
{
        WORD    regs[NREG-1];
        Example_MyData**        ret;
        uchar   temps[12];
        WORD    i;
};

Значение Example_MyData_map 0x40 означает битовую маску 010000…, т.е. первые 4 байта нашей структуры это не указатель (WORD) а вторые это указатель (String*).

libinterp/example.c

static Type* TMyData;
static uchar MyData_map[] = Example_MyData_map;

void
examplemodinit(void)
{
        ...
        TMyData = dtype(freeheap, Example_MyData_size, MyData_map, sizeof(MyData_map));
}

void
MyData_new(void *fp)
{
        F_MyData_new *f;
        int i;
        Example_MyData* mydata;

        f = fp;
        i = f->i;

        mydata = H2D(Example_MyData*, heap(TMyData));
        mydata->i = i;

        destroy(*f->ret);
        *f->ret = mydata;
}

testexample.b

...
example: Example;
MyData: import example;
...
init(nil: ref Draw->Context, nil: list of string)
{
        ...
        mydata := MyData.new(5);
        sys->print("i = %d, s = %q\n", mydata.i, mydata.s);
}

; testexample
...
i = 5, s = ''
;

Array

Рассмотрим работу с массивами. В памяти массив расположен следующим образом: heap-заголовок, array-заголовок, элементы массива. Соответственно, чтобы выделить память под массив необходимо знать размер и количество его элементов. Чтобы эти элементы проинициализировать (вдруг в них есть ссылки, которые надо выставить в H) и позже корректно удалить из памяти нужно знать тип этих элементов (тогда и размер указывать нет нужды, он уже указан внутри типа).

struct Array
{
        WORD    len;
        Type*   t;
        Array*  root;
        uchar*  data;
};

Здесь len это размер массива, t это тип его элементов, root указатель на родительский массив (если этот массив его срез), и data указатель на первый элемент массива (это следующий байт за структурой Array если массив самостоятельный или адрес первого элемента нашего среза среди элементов родительского массива).

Если мы создаём не срез другого массива, то нам необходимо выделить больше памяти, чем занимает сама структура Array (и, соответственно, чем указано в Tarray.size). Поэтому мы не сможем выделить память под массив через функцию heap() использовавшуюся ранее. К счастью, для этого есть удобная функция heaparray(). Пример выделения array[16] of byte:

Array *arr;
arr = H2D(Array*, heaparray(&Tbyte, 16));

Вот пример функции, возвращающей срез массива: http://code.google.com/p/inferno-cjson/source/browse/libinterp/cjson.c#59.

adt и ref adt

Есть неявное отличие между Limbo и C в том, как обрабатываются adt и ref adt. Если на уровне Limbo работа с ними выглядит (почти) одинаково:

a := array[10] of MyData;

b := array[10] of ref MyData;
for(i := 0; i < len b; i++)
        b[i] = ref MyData;

a[0].i = b[0].i;

то на уровне C это совершенно разные массивы:

Array *a, *b;
int i;
Example_MyData*  adata;
Example_MyData** bdata;

a = H2D(Array*, heaparray(TMyData, 10));
adata = (Example_MyData*)a->data;

b = H2D(Array*, heaparray(&Tptr,   10));
bdata = (Example_MyData**)b->data;
for(i = 0; i < b->len; i++)
        bdata[i] = H2D(Example_MyData*, heap(TMyData));

adata[0].i = bdata[0]->i;

GC

Общее описание tri-color алгоритма можно почитать в википедии. В Inferno эти три «цвета» называются mutator, marker и sweeper.

Новым объектам устанавливается h->color=mutator.

После каждого полного цикла gc значения переменных mutator, marker и sweeper изменяются по кругу, таким образом как бы меняя значения h->color всех объектов в heap:

mutator -> marker
marker  -> sweeper
sweeper -> mutator // этого не происходит т.к. все sweeper уже удалены

Если во время работы gc h->color==sweeper, то h удаляется из памяти.

Итак, что такое Setmark() и зачем он нужен.

#define Setmark(h)      if((h)->color!=mutator) { (h)->color = propagator; nprop=1; }

Далее, поскольку сборщик мусора может работать очень долго, и всё остальное в этот момент остановлено, то в Inferno сборщик мусора работает небольшими кусками — обойдя часть объектов он приостанавливается, давая поработать другому коду, а потом продолжает с того места, где остановился в прошлый раз. Но для данного алгоритма требуется проверить все объекты в памяти за один проход, атомарно, иначе невозможно однозначно определить неиспользуемые объекты. Поэтому в сборщике мусора Inferno реализован механизм, позволяющий определить, изменялись ли потенциально интересующие его объекты между запусками GC.

Этим механизмом и является вызов Setmark(). Выставляемый им при необходимости флаг nprop указывает GC, что по завершении текущего цикла обхода объектов в heap нельзя удалять не используемые объекты, а необходимо повторить цикл с начала.

Значение h->color==propagator означает, что при следующем запуске gc необходимо просмотреть этот объект. В процессе просмотра объекта h->color устанавливается в mutator. (Это же значение propagator выставляется «корневым» объектам в начале нового цикла GC, но в данном контексте это не важно.)

Отключение объекта в heap от GC

Поскольку GC удаляет из памяти все объекты на которые нет ссылок от «корневых» объектов (куда вероятно входят работающие нити Dis, подгруженные модули, etc.) не обращая внимания на значение их ref, то возникает вопрос: как хранить ссылку на heap-объект вне нитей Dis, например в глобальных переменных вашего C-модуля, так, чтобы её не убил GC? Для этого необходимо сообщить GC, что этот heap-объект он контролировать не должен с помощью poolimmutable() (для подключения объекта обратно к GC есть poolmutable(), все эти функции находятся в emu/port/alloc.c):

libinterp/example.c

...
static Array* EmptyArray;
 
void
examplemodinit(void)
{
        ...
        EmptyArray = H2D(Array*, heaparray(&Tbyte, 0));
        poolimmutable(D2H(EmptyArray));
}

Разработка модулей для Limbo на C (часть 2)