Pourquoi est-il "impossible" de mettre en œuvre le ramassage des ordures en C en raison de la faiblesse du typage ?

Question

Une personne plutôt intelligente m'a dit qu'il n'était pas possible d'implémenter le ramassage des ordures en C parce qu'il est faiblement typé. L'idée de base semble être que le C vous donne trop de liberté. Il a mentionné les pointeurs de casting sans vérification de type...

Je ne comprends pas vraiment l'idée. Je ne comprends pas vraiment l'idée. Quelqu'un peut-il me donner une explication et éventuellement un exemple de code expliquant pourquoi cela ne fonctionnerait pas ?

NOTE : Il est évident que le langage C est axé sur la vitesse et pourquoi voudriez-vous ajouter le ramassage des ordures ? Je suis simplement curieux.

Answer 1

Il faisait probablement référence au fait que l'on peut transformer un pointeur en un int et revenir au type de pointeur d'origine. Il est pratiquement impossible pour un GC de nettoyer correctement lorsque vous faites cela, considérez-le :

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 : L'opération ci-dessus ne produira qu'un pointeur suspendu avec un CG précis. Comme d'autres l'ont souligné, un collecteur conservateur peut toujours gérer correctement ce scénario car il suppose que tous qui pourrait être un pointeur valide est en fait un pointeur et ne libérera donc pas la mémoire allouée. Toutefois, cela n'est évidemment plus possible lorsque i est modifié de telle sorte qu'il ne ressemble plus à un pointeur valide pour le collecteur, par exemple de la manière suivante :

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

De plus, (comme d'autres l'ont souligné) il n'est impossible d'implémenter un CG pour le C que si l'on veut conserver toutes les fonctionnalités du langage. Si vous vous abstenez d'utiliser des astuces comme celles décrites ci-dessus (c'est-à-dire que vous vous limitez à un sous-ensemble d'opérations possibles), alors le CG est en effet réalisable.

Answer 2

Il est parfaitement possible d'implémenter n'importe quel gestionnaire de mémoire en C. Le problème est que vous devez alors utiliser exclusivement ses fonctions d'allocation et de désallocation et limiter votre "magie des pointeurs" aux éléments qu'il peut suivre. En outre, la gestion de la mémoire peut être limitée à certains types pris en charge.

Par exemple, le système retain/release et les pools autorelease de l'Objective-C sont fondamentalement des gestionnaires de mémoire mis en œuvre en C. De nombreuses bibliothèques mettent également en œuvre leur propre forme simple de gestion de la mémoire, comme le comptage de références.

Ensuite, il y a le collecteur d'ordures de Boehm. Pour l'utiliser, il suffit de remplacer votre malloc() / realloc() avec les versions Boehm et vous n'avez jamais besoin d'appeler free() à nouveau. Lire à ce sujet les problèmes éventuels liés à cette approche .

En outre, Consultez cette page wikipedia pour un aperçu rapide du fonctionnement des ramasseurs d'ordures conservateurs.

Answer 3

Si vous lisez les bons articles et que vous avez une licence en informatique, il est en fait assez facile de mettre en œuvre un système de gestion de l'information digne de ce nom. conservateur Le collecteur de déchets pour C J'ai une douzaine d'étudiants qui l'ont fait en tant qu'exercice de classe prenant environ quatre semaines. Ensuite, passez 20 ans à l'améliorer et vous obtiendrez le Boehm collector (libgc) .

L'idée de base est simple : s'il existe un motif de bits n'importe où dans un registre, sur la pile, dans une variable globale ou dans un objet du tas vivant, et que ce motif de bits se trouve être une adresse qui tombe à l'intérieur d'un objet alloué avec la fonction malloc que cet objet est considéré comme vivre . Tout objet qui n'est pas vivant ne peut pas être atteint par les pointeurs suivants, et peut donc être récupéré et utilisé pour répondre à de futures demandes d'allocation. Cette technique opère sur la représentation matérielle des pointeurs, et elle est complètement indépendant de la tipo des types de pointeurs ne sont pas pertinents ici.

Il est vrai qu'il y a une mise en garde : les techniques conservatrices de collecte de déchets peuvent être trompées en cachant délibérément des pointeurs. Compresser les structures contenant des pointeurs, conserver la seule copie d'un pointeur sur le disque, obscurcir un pointeur par XORing 0xdeadbeef Toutes ces techniques sont susceptibles d'ébranler un collectionneur conservateur. Mais ce type de problème est extrêmement rare, à moins qu'il ne soit posé délibérément. Les auteurs de compilateurs optimisants veillent généralement à ne pas cacher les pointeurs à un tel collecteur.

La partie la plus intéressante de votre question est la suivante pourquoi le faire . Trois raisons à cela :

• Il élimine la possibilité de nombreux bogues liés à la gestion de la mémoire.

• Il simplifie vos API car il n'est plus nécessaire de préciser qui alloue la mémoire, qui possède la mémoire allouée, s'il est nécessaire de copier la mémoire et qui est responsable de la libération de la mémoire.

• Croyez-le ou non, il peut être plus rapide que d'utiliser malloc y free .

Answer 4

Le problème est qu'il n'y a aucun moyen pour le système d'exécution de savoir avec certitude si un morceau de mémoire est référencé ou non. Même si vous enveloppez toutes les allocations de mémoire dans un code qui enregistre l'utilisation, vous pouvez toujours obtenir des pointeurs sur la mémoire utilisée par le biais d'une manipulation normale des pointeurs (ou par erreur). Les casts ne font que compliquer le problème pour le système d'exécution. Ainsi, si le runtime libère une partie de la mémoire, les choses vont se gâter pour tous les pointeurs qui pointent encore vers cette zone de la mémoire. Évidemment, la situation ne fait qu'empirer si l'on considère que le ramassage des ordures doit également fonctionner pour les applications multithreads.

Answer 5

Ce n'est pas impossible d'implémenter un ramasse-miettes pour le langage C (et en fait, ils existent, sous la forme d'un simple recherche sur google révèle), il est simplement difficile, parce qu'il peut être difficile de déterminer si une certaine chaîne de bits est un pointeur sur un bloc alloué ou simplement regards comme l'un d'entre eux.

La raison pour laquelle ce problème se pose est que le C (et le C++, d'ailleurs) vous permet de passer d'un type de pointeur à un type intégral, de sorte qu'une variable entière peut contenir une adresse dans un bloc alloué, empêchant le GC de libérer ce bloc, même si cette valeur n'était pas censée être un pointeur.

Par exemple, supposons qu'un bloc de mémoire soit alloué. Supposons que ce bloc de mémoire soit alloué à partir de l'adresse 0x00100000 (1 048 576) et qu'il ait une longueur de 1 Mo, c'est-à-dire qu'il s'étende jusqu'à 0x001FFFFF (2 097 151).

Supposons que je stocke également la taille d'un fichier image dans une variable (appelons-la fileSize). Ce fichier image fait 1,5 Mo (1 572 864 octets).

Ainsi, lorsque le ramasseur d'ordures s'exécutera, il rencontrera mon fileSize et décide qu'il ne peut pas libérer ce bloc, sous peine d'invalider mon pointeur peut-être. C'est parce que le GC ne sait pas si j'ai fait cela :

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

ou si je viens de le faire :

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

Dans ce dernier cas, il est possible de libérer le bloc à *mem (s'il n'existe pas d'autres références), alors que dans le premier cas, ce n'est pas le cas. Il faut être conservateur et supposer que ce n'est pas le cas, donc la mémoire "fuit" (au moins jusqu'à ce que fileSize sorte du champ d'application ou soit modifié pour une valeur en dehors du bloc alloué).

Mais les collecteurs d'ordures pour le C (et le C++) do existent. La question de savoir s'ils sont utiles ou non est un autre sujet de discussion.