Многие языки семейства Оберон включают в себя сборщик мусора. В основном используется алгоритм Mark-and-Sweep. Сам по себе этот алгоритм не сложный, он основывается на том, что у нас имеется множество начальных указателей, с которых мы начинаем помечать объекты, как используемые, и так далее, если у объекта есть свои указатели, то и эти объекты помечаем как используемые. Далее можно добавить в список свободной памяти все объекты, которые оказались не помеченными.
Нахождение начального множества указателей не такое простое дело, как кажется. Это множество включает в себя глобальные переменные-указатели, локальные переменные-указатели, возможно, регистры, если в них временно хранится какой-нибудь указатель, который нигде больше не хранится. Множество глобальных переменных-указателей обычно сохраняется определенным образом в объектный файл и загручик получает эту информацию из объектного файла и соотвественно сборщик мусора знает, какие из глобальных переменных являются указателями.
А вот как определить какие из локальных переменных являются указателями?
Во многих книгах Никлауса Вирта, этот вопрос как-то обходится стороной. Например, в книге Project Oberon по поводу начальных указателей написано: "We shall postpone the question of how these roots are to be found, and first present a quick tutorial about tree traversal."
Возможно, в книге где-то упоминается реализация поиска начальных указателей в локальных переменных, просто я не нашел. Если кто укажет мне на раздел в книге и страницу, буду очень благодарен.
Возможно, у него есть отдельная статья, где он подробно описывает устройство сборщика мусора.
Проверил, как сборщик мусора устроен в системе BlackBox. В модуле Kernel есть следующая функция:
Код:
PROCEDURE MarkLocals;
VAR sp, p, min, max: INTEGER; c: Cluster;
BEGIN
S.GETREG(FP, sp); nofcand := 0; c := root;
WHILE c.next # NIL DO c := c.next END;
min := S.VAL(INTEGER, root); max := S.VAL(INTEGER, c) + c.size;
WHILE sp < baseStack DO
S.GET(sp, p);
IF (p > min) & (p < max) & (~strictStackSweep OR (p MOD 16 = 0)) THEN
candidates[nofcand] := p; INC(nofcand);
IF nofcand = LEN(candidates) - 1 THEN CheckCandidates; nofcand := 0 END
END;
INC(sp, 4)
END;
candidates[nofcand] := max; INC(nofcand); (* ensure complete scan for interface mark*)
IF nofcand > 0 THEN CheckCandidates END
END MarkLocals;
Из которой следует, что проверяются не только указатели а все значения в стеке с шагом 4 байта. Если значение хранящееся в 4-х байтах лежит в интервала от min до max, то возможно это указатель и с него надо начинать проверку.
Как мне кажется это не совсем правильный алгоритм, так как если в какой-то переменной случайно окажется значение равное указателю на память, которое больше не используется, то память не будет освобождена, пока эта переменная не изменит свое значение.
Например, можно проделать следующий эксперимент:
Процедура внутри себя выделяет 600 мегабайт и вызывает себя рекурсивно, пока удается выделить память, или пока количество вызовов не достигнет 10. В данном примере, у меня выделяется 2 раза по 600 мегабайт, больше не может выделиться.
Код:
MODULE TestCollector;
IMPORT Kernel, SYSTEM, Log;
PROCEDURE Alloc(n: INTEGER);
VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
a: INTEGER;
BEGIN
IF n < 10 THEN
NEW(p);
IF p # NIL THEN
Log.String("OK"); Log.Ln;
Alloc(n+1);
ELSE
Log.String("FAIL"); Log.Ln;
END;
END;
END Alloc;
PROCEDURE Do*;
BEGIN
Alloc(0);
END Do;
END TestCollector.
Немного изменю программу. Теперь указателю присваивается NIL, и теоретически процедура может очень много раз себя вызвать, так как стоит ограничение 10 раз, то она выполнится 10 раз и остановится.
Код:
MODULE TestCollector;
IMPORT Kernel, SYSTEM, Log;
PROCEDURE Alloc(n: INTEGER);
VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
a: INTEGER;
BEGIN
IF n < 10 THEN
NEW(p);
IF p # NIL THEN
p := NIL;
Log.String("OK"); Log.Ln;
Alloc(n+1);
ELSE
Log.String("FAIL"); Log.Ln;
END;
END;
END Alloc;
PROCEDURE Do*;
BEGIN
Alloc(0);
END Do;
END TestCollector.
А теперь рассматривается случай, когда в переменной типа INTEGER случайно оказалось значение равное указателю. Этот пример отработает только 2 раза, хотя по логике должен был бы отработать 10 раз, как и предыдущий пример.
Код:
MODULE TestCollector;
IMPORT Kernel, SYSTEM, Log;
PROCEDURE Alloc(n: INTEGER);
VAR p: POINTER TO ARRAY 150000000 OF INTEGER;
a: INTEGER;
BEGIN
IF n < 10 THEN
NEW(p);
IF p # NIL THEN
a := SYSTEM.VAL(INTEGER, p);
p := NIL;
Log.String("OK"); Log.Ln;
Alloc(n+1);
ELSE
Log.String("FAIL"); Log.Ln;
END;
END;
END Alloc;
PROCEDURE Do*;
BEGIN
Alloc(0);
END Do;
END TestCollector.
В общем основной вопрос этого большого топика в том, как правильно реализовать поиск указателей в локальных переменных?