Почему "невозможно" реализовать сборку мусора в C из-за слабого набора текста?

Ответ 1

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

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. Как отмечали другие, консервативный сборщик все же может правильно справиться с этим сценарием, поскольку предполагает, что любой битовый шаблон, который может быть действительным указателем, на самом деле является указателем и, таким образом, не освобождает выделенную память. Однако это, конечно, уже невозможно, когда я дополнительно модифицирован так, что он больше не выглядит как действительный указатель на коллектор, например. следующим образом:

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 действительно выполнимо.

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

• Это исключает возможность множества ошибок памяти.

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

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 (и С++) do существуют. Независимо от того, ценны они или нет, это вопрос для другого обсуждения.

Ответ 6

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

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

Ответ 7

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);
}

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