Wie befinden sich Speicherreferenzen in einer Implementierung von beweglicher Speicherbereinigung?

Question

In einem sich bewegenden Garbage Collector muss unbedingt genau unterschieden werden, welche Werte auf dem Stapel und dem Heap Referenzen sind und welche unmittelbaren Werte sind. Dies ist ein Detail, das in der meisten Literatur, die ich über die Garbage Collection gelesen habe, beschönigt zu sein scheint.

Ich habe untersucht, ob das Zuweisen einer Präambel zu jedem Stapelrahmen funktionieren würde, zum Beispiel das Beschreiben jedes Arguments, bevor es aufgerufen wird. Aber das alles bringt das Problem auf eine höhere Ebene der indirekten Ebene. Wie unterscheidet man dann die Präambel von dem Stapelrahmen, wenn sie während eines GC-Zyklus für unmittelbare Werte oder Referenzen durchlaufen wird?

Kann jemand erklären, wie dies in der realen Welt umgesetzt wird? Hier

ist ein Beispielprogramm für dieses Problem eine erstklassige Funktion lexikalische Verschluss mit und ein Diagramm der Stapelrahmen und und Eltern-Umgebung befindet sich auf dem Heap:

Ein Beispielprogramm

def foo(x) = { 
    def bar(y,z) = { 
     return x + y + z 
    } 
    return bar 
} 


def main() = { 
    let makeBar = foo(1) 
    makeBar(2,3) 
} 

Bar des Stapelrahmen am Punkt des Aufrufs:

In diesem Beispiel hat der Stack-Rahmen von bar eine lokale Variable, x, die einen Zeiger auf einen Wert auf dem Heap darstellt, wobei die Argumente y und z unmittelbare Ganzzahlwerte sind.

Ich lese, dass Objective CAML verwendet ein Tag-Bit für jeden Wert auf dem Stapel platziert, die jedem Wert vorangestellt. Zulassen einer binären ref-or-imm-Prüfung für jeden Wert während eines GC-Zyklus. Dies kann jedoch unerwünschte Nebenwirkungen haben. Ganzzahlen sind auf 31 Bit beschränkt und die dynamische Codegenerierung für Grundelementberechnungen müsste angepasst werden, um dies zu kompensieren. Kurz gesagt - es fühlt sich ein wenig zu dreckig an. Es muss eine elegantere Lösung geben.

Ist es möglich, diese Informationen statisch zu kennen und darauf zuzugreifen? Wie etwa die Typinformation irgendwie an den Garbage Collector zu übergeben?

Answer 1

Kann jemand erklären, wie dies in der realen Welt umgesetzt wird?

Es gibt mehrere mögliche Ansätze

• konservative Stapel Scannen. Alles wird als potenzieller Zeiger behandelt. Dies führt dazu, dass ein GC ungenau ist. Ungenaues Scannen verhindert, dass Objekte verschoben werden, was wiederum die Implementierung von semi-space/compacting GCs verhindert oder verkompliziert.
• markieren Bits wie Sie erwähnt haben. dies kann als etwas weniger konservatives Abtasten angesehen werden, aber es ist immer noch ungenau
• der Compiler behält Kenntnis des genauen Stapellayouts, d. h. wo Zeiger zu jeder gegebenen Zeit lokalisiert sind. Da dies von Instruktion zu Instruktion wechseln kann und Zeiger auch in Registern liegen können, wäre dies sehr komplex.
  Zur Vereinfachung wird nur für bestimmte Punkte vorgegangen, an denen alle Threads kooperativ die Kontrolle an den GC mit einem bekannten Stack-Layout übergeben können, wenn ein GC von einem anderen Thread angefordert wird. Dies wird als Sicherheitspunkt bezeichnet (nachstehend erläutert).
• andere Mechanismen möglich sein könnten, z.B. den Stapel Aufteilung in Referenz- und Nicht-Referenzeinträge und immer sicherstellen, dass enregistered Referenzen auch irgendwo auf dem Stapel sind, aber ich weiß nicht, wie praktisch, dass Ansatz

Gil Tene ist hat eine schöne, wenn auch meist JVM-spezifische Erklärung dessen, was ein Sicherungspunkt ist, so werde ich die relevanten Teile hier zitieren:

hier ist eine Sammlung von Aussage über „was ist ein Sicherungspunkt“, dass Versuch richtig und etwas genauer zu sein:

1. Ein Thread kann sich an einem sicheren Punkt befinden oder nicht an einem sicheren Punkt sein. Bei einem Sicherheitspunkt ist die Darstellung des Java-Maschinenzustands des Threads gut beschrieben und kann von anderen Threads in der JVM sicher manipuliert und beobachtet werden. Wenn kein Safepoint vorhanden ist, wird die Darstellung des Java-Maschinenzustands NICHT durch andere Threads in der JVM manipuliert. [Beachten Sie, dass andere Threads den tatsächlichen logischen Maschinenzustand eines Threads nicht manipulieren, sondern nur die Darstellung von diesem Status. Ein einfaches Beispiel für das Ändern der Repräsentation des Zustands der Maschine besteht darin, die virtuellen Adressen zu ändern, auf die ein Java-Referenzstack als Ergebnis des Verschiebens dieses Objekts zeigt. Der logische Zustand der Referenzvariable ist von dieser Änderung nicht betroffen, da sich die Referenz immer noch auf das gleiche Objekt bezieht und zwei Referenzvariablen , die sich auf dasselbe Objekt beziehen, logisch immer noch logisch anderen sind, selbst wenn sie temporär zeigen zu verschiedenen virtuellen Adressen].

[...]

7. All [praktische] JVMs gilt einig sehr effizienten Mechanismus für häufig überqueren Safepoint-Möglichkeiten, wo der Faden nicht tatsächlich einen Sicherungspunkt eingeben es sei denn, jemand anderes weist auf die Notwendigkeit dies zu tun. Z.B. die meisten Call-Sites und Loop Backedges im generierten Code enthalten eine Art von Sicherheitsabfrage Sequenz, die sich auf "Do I muss jetzt zu einem Sicherheitspunkt gehen?" Viele HotSpot-Varianten (OpenJDK und Oracle JDK) verwenden derzeit ein einfaches globales "go to safepoint" Indikator in Form einer Seite, die geschützt ist, wenn ein Sicherheitspunkt benötigt wird, und ansonsten ungeschützt. Die Safepoint-Abfrage für diesen Mechanismus ergibt eine Belastung von einer festen Adresse auf dieser Seite. Wenn die Last mit einem SEGV abfängt, weiß der Thread, dass er einen Sicherheitspunkt eingeben muss. Zing verwendet einen anderen Go-to-Safepoint-Indikator pro Thread mit ähnlicher Effizienz wie .

[...]

Answer 2

Die Antwort oben identifiziert die drei wichtigsten Alternativen. Es ist eine Variante der 3.en Alternativen, die versucht wurde:

• Haben Sie die Compiler-Partition/neu ordnet die Variablen in dem Stapel und Rahmen-Objekt, sodass (zum Beispiel) die Referenzvariablen vor dem Skalarvariablen kommen.

Das bedeutet, dass die Typinformation, die zur Laufzeit beibehalten werden muss, eine einzelne Zahl ist. Dies könnte in dem Rahmen selbst oder als Typinformation, die mit der Klasse oder der Methode verbunden ist, auf normale Weise gespeichert werden. Dies bringt jedoch andere Gemeinkosten mit sich; z.B. die Notwendigkeit für Dual-Stacks und Stack-Pointer. Empirisch ist es kein Gewinn.

Einige andere Punkte:

• Das Problem der Identifizierung von Referenzen für alle Arten von GC vorhanden ist.

• Wenn Sie den "konservativen" Ansatz (bei dem die Referenzidentifikation ungenau sein kann) herunterfahren, können Sie den Heap nicht sicher komprimieren. Dies beinhaltet alle Arten von Kopierern.

• Mark Bits (sofern sie nicht hardwaregestützt sind) können für effiziente arithmetische Operationen problematisch sein. (Wenn Sie ein bisschen "stehlen" müssen, um Zeiger und Nicht-Zeiger zu unterscheiden, dann erfordern arithmetische Operationen zusätzliche Anweisungen zur Kompensation. FWIW, der MIT-CLU-Compiler, der dazu verwendet wurde ... in den 1980er Jahren. Der CLU-GC war ein genaue Markierung/Sweep/Kompaktkollektor, aber integer-Arithmetik war langsam ... und ich kann mich nicht erinnern, wie sie mit Floating-Point-behandelt)

Answer 3

ich einen weiteren möglichen Ansatz als Emery's Idea beschrieben entdeckt.

• Führen Sie zwei Kopien eines Programms aus. Überprüfen Sie beim Überprüfen eines vermuteten Zeigers beide Kopien des Speichers.
• Wenn der betreffende int/Zeiger in beiden Programmen gleich ist, ist es ein int.
• Wenn der Int/Zeiger dieselbe Basis aber einen anderen Offset hat, dann ist es ein Zeiger.

kann ich dies mit erheblichen Leistungsaufwand in der realen Welt Beispiele sehen, aber für die sequentielle Sprachen möglich sein könnte, oder solche, die gleichzeitig in User-Space auf einem einzigen Kern laufen eine Reduktion Timer-Ansatz.