Часть 1
Чтобы на C корректно создавать и уничтожать сложные структуры, с которыми будет работать код на Limbo, необходимо представлять себе как они хранятся в памяти, т.е. как организован heap в Inferno. Все упомянутые ниже функции для работы с heap описаны в
Для того, чтобы просто выделить
Физически в памяти при этом будет выделено 256 + размер heap-заголовка байт, и в начале будет лежать заголовок, а потом пользовательские данные. Заголовок описан в структуре
Что же находится в заголовке heap? Про
Для начала пара слов о сборщике мусора в Inferno. Используются одновременно две стратегии: простой счётчик ссылок которого достаточно для большинства структур, плюс вариация на тему tri-colour marking для подбирания структур с цикличными ссылками. Соответственно,
Соответственно, пока вы храните значение возвращённое
Разумеется, если вы выделили объект в heap, а потом вернули его пользователю записав в
Есть один неявный нюанс связанный с перемещением ссылок. В предыдущем примере с возвращаемым значением происходит перемещение новой, только что созданной ссылки, и ничего дополнительного там не требуется. Но если вы переместили ссылку из одной уже существующей переменной/структуры в другую, тоже уже существующую, то необходимо уведомить об этом tri-colour алгоритм вызовом
Описанный выше пример с
Все объекты в heap, с которыми может оперировать Limbo, должны относится к какому-нибудь типу, описанному структурой
Для стандартных типов (любая adt/кортеж/структура, которая содержит либо не ссылочные поля, либо поля со ссылками на обычные heap-объекты которые можно освободить через
Некоторые типы данных используют память не совсем стандартным способом. Типичные примеры это
Поле
Поле
Значения
Типы для ваших собственных adt/кортежей/структур в некоторых случаях поможет определить
Значение Example_MyData_map 0x40 означает битовую маску 010000…, т.е. первые 4 байта нашей структуры это не указатель (WORD) а вторые это указатель (String*).
Рассмотрим работу с массивами. В памяти массив расположен следующим образом: heap-заголовок, array-заголовок, элементы массива. Соответственно, чтобы выделить память под массив необходимо знать размер и количество его элементов. Чтобы эти элементы проинициализировать (вдруг в них есть ссылки, которые надо выставить в
Здесь
Если мы создаём не срез другого массива, то нам необходимо выделить больше памяти, чем занимает сама структура
Вот пример функции, возвращающей срез массива: http://code.google.com/p/inferno-cjson/source/browse/libinterp/cjson.c#59.
Есть неявное отличие между Limbo и C в том, как обрабатываются adt и ref adt. Если на уровне Limbo работа с ними выглядит (почти) одинаково:
то на уровне C это совершенно разные массивы:
Общее описание tri-color алгоритма можно почитать в википедии. В Inferno эти три «цвета» называются
Новым объектам устанавливается
После каждого полного цикла gc значения переменных
Если во время работы gc
Итак, что такое
Далее, поскольку сборщик мусора может работать очень долго, и всё остальное в этот момент остановлено, то в Inferno сборщик мусора работает небольшими кусками — обойдя часть объектов он приостанавливается, давая поработать другому коду, а потом продолжает с того места, где остановился в прошлый раз. Но для данного алгоритма требуется проверить все объекты в памяти за один проход, атомарно, иначе невозможно однозначно определить неиспользуемые объекты. Поэтому в сборщике мусора Inferno реализован механизм, позволяющий определить, изменялись ли потенциально интересующие его объекты между запусками GC.
Этим механизмом и является вызов
Значение
Поскольку GC удаляет из памяти все объекты на которые нет ссылок от «корневых» объектов (куда вероятно входят работающие нити Dis, подгруженные модули, etc.) не обращая внимания на значение их
Содержание
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)); }