Почему «невозможно» реализовать сборку мусора в C из-за слабой типизации? - PullRequest
Новая
       13

Почему «невозможно» реализовать сборку мусора в C из-за слабой типизации?

21 голосов
/ 10 января 2009

Мне сказал довольно умный человек, что вы не можете реализовать сборку мусора в C из-за ее слабой типизации. Кажется, основная идея в том, что C дает вам слишком много свободы. Он упомянул указатели приведения без проверки типа ...

Я не очень понимаю эту идею. Может кто-нибудь дать мне объяснение и, возможно, пример кода, почему это не сработает.

ПРИМЕЧАНИЕ: Очевидно, что C - это скорость, и почему вы хотите добавить сборку мусора? Мне просто любопытно.

Ответы [ 7 ]

24 голосов
/ 10 января 2009

Он, вероятно, ссылался на тот факт, что вы можете привести указатель к типу int и вернуться к исходному типу указателя. Когда вы это делаете, сборщик мусора не может правильно очистить, подумайте: 

char * p = (char *) malloc(16);
int i = (int) p;
p = 0;
// GC runs and finds that the memory is no longer referenced
p = (char *) i;
// p is now a dangling pointer

РЕДАКТИРОВАТЬ : Приведенное выше описание приведет только к свисающему указателю с точным ГХ. Как уже отмечали другие, консервативный сборщик все еще может правильно обрабатывать этот сценарий, поскольку он предполагает, что любой битовый шаблон, который может быть действительным указателем, на самом деле является указателем и, таким образом, не освобождает выделенную память. Однако, это, конечно, больше невозможно, когда я дополнительно изменен так, что он больше не выглядит как действительный указатель на коллектор, например, следующим образом: 

char * p = (char *) malloc(16);
int i = ~((int) p);
p = 0;
// GC runs and finds that the memory is no longer referenced
p = (char *) ~i;
// p is now a dangling pointer

Более того, (опять же, как уже отмечали другие), реализовать GC для C невозможно, только если вы хотите сохранить полную функциональность языка. Если вы воздерживаетесь от использования трюков, подобных описанным выше (то есть вы ограничиваетесь набором возможных операций), тогда GC действительно выполним.

12 голосов
/ 11 января 2009

Вполне возможно реализовать любой менеджер памяти, о котором вы можете подумать в C. Подвох в том, что вам придется использовать только его функции выделения / освобождения и ограничивать свою «магию указателей» вещами, которые он может отслеживать. Кроме того, управление памятью может быть ограничено определенными поддерживаемыми типами.

Например, система хранения / освобождения Objective-C и пулы автоматического освобождения в основном являются менеджерами памяти, реализованными в C. Многие библиотеки также реализуют свою собственную простую форму управления памятью, такую ​​как подсчет ссылок.

Тогда есть сборщик мусора Бём. Чтобы использовать его, просто замените ваши звонки malloc() / realloc() версиями Boehm, и вам больше никогда не придется звонить free(). Прочитайте о возможных проблемах с этим подходом .

Кроме того, проверьте эту страницу википедии для быстрого обзора того, как работают консервативные сборщики мусора.

6 голосов
/ 11 января 2009

Если вы читаете правильные статьи и у вас есть степень бакалавра по CS, на самом деле довольно легко реализовать приличный консервативный сборщик мусора для C --- У меня есть дюжина студентов, которые сделали это как занятие заняло около четырех недель. Затем потратите 20 лет на его улучшение, и вы получите Boehm сборщик (libgc) .

Основная идея проста: если где-то в регистре, в стеке, в глобальной переменной или в объекте динамической кучи есть битовый шаблон, и этот битовый шаблон является адресом, который попадает внутрь объекта выделено malloc, чем этот объект считается live . Любой объект, который не является живым, не может быть достигнут с помощью указателей, и поэтому его можно восстановить и использовать для удовлетворения будущих запросов на выделение. Этот метод работает с аппаратным представлением указателей, и он полностью независимо от типа типов указателей - здесь не имеют значения.

Правда, есть предостережение: консервативные методы сбора мусора можно обмануть, умышленно скрывая указатели. Сжатие структур, содержащих указатели, сохранение единственной копии указателя на диске, запутывание указателя с помощью XORing 0xdeadbeef, и все эти методы сломают консервативный сборщик. Но такого рода проблемы встречаются крайне редко, если они не сделаны намеренно. Авторы оптимизирующих компиляторов обычно стараются не скрывать указатели от такого сборщика.

Самая интересная часть вашего вопроса - зачем это делать . Три причины:

  • Исключает возможность многих ошибок управления памятью.

  • Это упрощает ваши API , поскольку больше не нужно указывать, кто выделяет память, кому принадлежит выделенная память, нужно ли копировать память и кто отвечает за ее освобождение.

  • Верьте или нет, это может быть быстрее , чем при использовании malloc и free.

3 голосов
/ 11 января 2009

Это не невозможно реализовать сборщик мусора для C (и на самом деле они существуют, как показывает простой поиск в Google ), это просто сложно, потому что это может быть Трудно определить, является ли определенная строка битов указателем на выделенный блок или просто выглядит как единица.

Причина, по которой это является проблемой, заключается в том, что C (и C ++, в этом отношении) позволяет вам приводить тип указателя к целочисленному типу, поэтому целочисленная переменная может содержать адрес в выделенном блоке, предотвращая GC от освобождение этого блока, даже если это значение не предназначено для указателя.

Например, допустим, у меня выделен блок памяти. Предположим, что этот блок памяти выделен, начиная с адреса 0x00100000 (1 048 576), и имеет длину 1 МБ, поэтому расширяется до 0x001FFFFF (2 097 151).

Допустим, я также сохраняю размер файла изображения в переменной (назовем это fileSize). Размер этого файла изображения составляет 1,5 МБ (1 572 864 байта).

Таким образом, при запуске сборщика мусора он встретит мою переменную fileSize, найдет ее, содержащую значение, соответствующее адресу в моем выделенном блоке, и решит, что он не может освободить этот блок, чтобы он не сделал недействительным мой указатель Maybe. , Это потому, что сборщик мусора не знает, сделал ли я это: 

int fileSize;
{
    char *mem = (char*)malloc(1048576);
    fileSize = (int)(mem + 524288);
}
// say GC runs here

или, если я только что сделал это: 

int fileSize;
{
    char *mem = (char*)malloc(1048576);
    fileSize = 1572864;
}
// say GC runs here;

В последнем случае безопасно освободить блок в * mem, (если нет других ссылок), тогда как в первом это не так. Он должен быть консервативным и предполагать, что это не так, поэтому память «протекает» (по крайней мере до тех пор, пока fileSize не выйдет из области или не изменится на значение вне выделенного блока).

Но сборщики мусора для C (и C ++) do существуют. Являются ли они ценными, вопрос другого обсуждения.

3 голосов
/ 11 января 2009

Проблема в том, что среда выполнения не может точно знать, есть ли ссылка на какой-либо фрагмент памяти или нет. Даже если вы распределите всю память в коде, который регистрирует использование, вы все равно можете получить указатели на использованную память с помощью регулярных манипуляций с указателями (или по ошибке). Кастинги только усложняют задачу во время выполнения. Поэтому, если среда выполнения освобождает часть памяти, она испортит все указатели, все еще указывающие на эту область памяти. Очевидно, что ситуация только ухудшается, если учесть, что сборка мусора должна работать и для многопоточных приложений.

2 голосов
/ 11 января 2009

Невозможно реализовать точный сборщик мусора для C из-за свобод, предоставляемых указателями C, и того факта, что длина массива C является чьим-либо предположением. Это означает, что многие сложные подходы сборки мусора не могут быть использованы. (На ум приходят копирование и сжатие сборщиков мусора.)

Однако возможно реализовать консервативный сборщик мусора ( boehm ), который в основном предполагает, что все, что выглядит как указатель, является указателем. Это не очень эффективно, но работает для достаточно мягкого определения «работ».

0 голосов
/ 11 января 2009

C не является слабо типизированным, но этот код иллюстрирует сложность встраивания сборщика мусора в язык: 

#include <stdio.h>
#include <stdlib.h>

int GetSomeMemory() {
    char* pointerToHeapMemory = malloc(10);
    return (int)pointerToHeapMemory;
}

int main() {
    int memoryAddress = GetSomeMemory();

    /* at this point a garbage collector might decide to clear up the memory that
     * was allocated in GetSomeMemory on the grounds that pointerToHeapMemory 
     * is no longer in scope. But the truth is we still know about that memory and 
     * we're about to use it again... */

    char* anotherPointerToHeapMemory = (char*) memoryAddress;

    sprintf(anotherPointerToHeapMemory, "123456789\0");
    printf("%s\n", anotherPointerToHeapMemory);
}

Сборка мусора может быть выполнена до тех пор, пока все работающие над проектом соглашаются избегать такого рода вещей и используют общий набор функций для выделения и доступа к памяти. Например, это реализация сборщика мусора C

...