traduccion - ¿Por qué es "imposible" implementar recolección de basura en C debido a tipeo débil?

garbage collector wordpress

Question

Una persona bastante inteligente me dijo que no puedes implementar la recolección de basura en C porque está débilmente tipada. La idea básica parece ser que C te da demasiada libertad. Mencionó indicadores de lanzamiento sin verificación de tipo ...

Realmente no entiendo la idea. ¿Puede alguien darme una explicación y posiblemente una muestra del código de por qué esto no funcionaría?

NOTA: Obviamente, C tiene que ver con la velocidad y ¿por qué le gustaría agregar la recolección de basura? Solo tengo curiosidad.

Answer 1

Es imposible implementar un recolector de basura preciso para C debido a las libertades otorgadas a los indicadores de C y al hecho de que la longitud de una matriz C es una incógnita. Esto significa que muchos enfoques sofisticados de recolección de basura no pueden ser utilizados. (Copiar y compactar recolectores de basura vienen a la mente).

Sin embargo, es posible implementar un recolector de basura conservador ( boehm ), que básicamente asume que todo lo que parece ser un puntero es un puntero. Esto no es muy eficiente, pero funciona para una definición de "obras" adecuadamente indulgente.

Answer 2

No es imposible implementar un recolector de basura para C (y de hecho, existen, como lo revela una simple búsqueda en Google ), simplemente es difícil, porque puede ser difícil determinar si una determinada cadena de bits es un puntero hacia un destino asignado. bloquear o simplemente se ve como uno.

La razón por la cual esto es un problema es porque C (y C ++, para el caso) le permite convertir de un tipo de puntero a un tipo integral, por lo que una variable entera puede contener una dirección dentro de un bloque asignado, evitando que el GC libere ese bloque , a pesar de que ese valor no estaba destinado a ser un puntero.

Por ejemplo, digamos que tengo asignado un bloque de memoria. Supongamos que este bloque de memoria se asigna comenzando en la dirección 0x00100000 (1,048,576) y tiene 1 MB de longitud, por lo que se extiende a 0x001FFFFF (2,097,151).

Digamos que también estoy almacenando el tamaño de un archivo de imagen en una variable (llamémoslo fileSize). Este archivo de imagen tiene 1,5 MB (1,572,864 bytes).

Entonces, cuando se ejecuta el recolector de basura, se encontrará con mi variable fileSize , encontrará que contiene un valor que corresponde a una dirección dentro de mi bloque asignado y decidirá que no puede liberar este bloque, para que no invalide mi puntero. Eso es porque el GC no sabe si he hecho esto:

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

o si acabo de hacer esto:

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

En este último caso, es seguro liberar el bloque en * mem, (si no existen otras referencias), mientras que en el primero, no lo es. Debe ser conservador y asumir que no lo es, por lo que la memoria "pierde" (al menos hasta que FileSize se salga del alcance o se cambie a un valor fuera del bloque asignado).

Pero existen recolectores de basura para C (y C ++). Si son valiosos o no es un tema para una discusión diferente.

Answer 3

Probablemente se refirió al hecho de que puede convertir un puntero a un int y volver al tipo de puntero original. Es casi imposible para un GC limpiar correctamente cuando haces eso, considera:

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

EDITAR : Lo anterior solo producirá un puntero colgante con un GC preciso. Como han señalado otros, un recopilador conservador puede manejar correctamente este escenario, ya que supone que cualquier patrón de bits que podría ser un puntero válido en realidad es un puntero y, por lo tanto, no liberará la memoria asignada. Sin embargo, esto ya no es posible cuando sigo modificándolo de manera que ya no se ve como un puntero válido para el recopilador, por ejemplo, de la siguiente manera:

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

Además, (de nuevo, como otros han señalado), es imposible implementar un GC para C si desea conservar la funcionalidad completa del lenguaje. Si se abstiene de utilizar trucos como el anterior (es decir, se limita a un subconjunto de las posibles operaciones) entonces GC es efectivamente factible.

Answer 4

C no tiene una escritura débil, pero este código ilustra la dificultad de construir un recolector de basura en el idioma:

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

La recolección de basura se puede hacer siempre que todos los que trabajan en un proyecto acepten evitar este tipo de cosas y utilicen un conjunto común de funciones para asignar y acceder a la memoria. Por ejemplo, esta es una implementación de colector de basura C

Answer 5

Es perfectamente posible implementar cualquier gestor de memoria que se le ocurra en C. Lo atrapado es que luego tiene que usar sus funciones de asignación / desasignación exclusivamente y restringir su "magia de puntero" a cosas que puede hacer un seguimiento. Además, la administración de la memoria puede estar restringida a ciertos tipos admitidos.

Por ejemplo, Objective-C''s retiene / libera sistemas y autorelease pools son básicamente administradores de memoria implementados en C. Muchas bibliotecas también implementan su propia forma simple de administración de memoria, como el conteo de referencias.

Luego, está el recolector de basura Boehm. Para usarlo, solo reemplace sus llamadas malloc() / realloc() con las versiones Boehm y nunca más tendrá que volver a llamar a free() . Lea sobre los posibles problemas con este enfoque .

Además, consulte esta página de wikipedia para obtener una descripción general rápida de cómo funcionan los recolectores de basura conservadores.

Answer 6

Si lees los documentos correctos y tienes una licenciatura en CS, en realidad es bastante fácil implementar un recolector de basura conservador decente para C --- Tengo una docena de estudiantes que lo han hecho como un ejercicio de clase que toma aproximadamente cuatro semanas. Luego pasa 20 años mejorando y obtendrás el recopilador Boehm (libgc) .

La idea básica es simple: si hay un patrón de bits en cualquier lugar de un registro, en la pila, en una variable global o en un objeto dinámico en vivo, y ese patrón de bits pasa a ser una dirección que cae dentro de un objeto asignado con malloc , que ese objeto se considera en vivo . Cualquier objeto que no esté activo no puede ser alcanzado por los siguientes punteros, por lo que puede recuperarse y utilizarse para satisfacer futuras solicitudes de asignación. Esta técnica opera en la representación del hardware de los punteros, y es completamente independiente del tipo de puntero. Los tipos son irrelevantes aquí.

Es cierto que hay una advertencia: las técnicas conservadoras de recolección de basura pueden ser engañadas ocultando deliberadamente los punteros. Comprima las estructuras que contienen punteros, mantenga la única copia de un puntero en el disco, ofusque un puntero mediante 0xdeadbeef , y todas estas técnicas romperán un recopilador conservador. Pero este tipo de problema es extremadamente raro a menos que se haga deliberadamente. Los autores de los compiladores de optimización suelen tener cuidado de no ocultar los punteros de dicho recopilador.

La parte más interesante de tu pregunta es por qué hacerlo . Tres razones:

• Elimina la posibilidad de muchos errores de gestión de memoria.

• Simplifica sus API porque ya no es necesario especificar quién asigna la memoria, a quién pertenece la memoria asignada, si es necesario copiar la memoria y quién es responsable de liberar la memoria.

• Lo creas o no, puede ser más rápido que usar malloc y free .

Answer 7

El problema es que no hay forma de que el tiempo de ejecución sepa con certeza si se hace referencia a alguna parte de la memoria o no. Incluso si ajusta toda la asignación de memoria en el código que registra el uso, aún puede obtener punteros a la memoria utilizada a través de la manipulación regular del puntero (o por error). Los lanzamientos solo hacen que el problema sea más difícil para el tiempo de ejecución. Entonces, si el tiempo de ejecución libera un trozo de memoria, ensuciará las cosas para los punteros que aún apuntan a esa área de memoria. Obviamente, la situación solo empeora cuando se considera que la recolección de basura también debe funcionar para aplicaciones de subprocesos múltiples.