Zum Inhalt springen

Speicherzuordnung für RDM 14.2

Einführung

Der Speicherzuweiser für RDM vor 14.2 wurde in erster Linie auf Flexibilität und nicht auf Geschwindigkeit ausgelegt. In bestimmten Fällen kann die Leistung dramatisch sinken. Eine Funktion, die wir aus diesem neuen Speicherzuweiser entfernt haben, ist die Möglichkeit, Speicher mithilfe eines Handles zuzuweisen und später den gesamten Speicher, der demselben Handle zugeordnet ist, auf einmal freizugeben. Während diese Funktion es einfach machte, harte Speicherlecks zu vermeiden (Speicher, der bei Beendigung nicht freigegeben wird), hatten wir häufig weiche Speicherlecks (Speicher, der nach einer bestimmten Bedingung nicht verwendet wird, aber schließlich freigegeben wird).

In RDM 14.2 haben wir einen neuen Speicherzuweiser entwickelt, um die Probleme zu lösen, die wir mit dem alten Speicherzuweiser hatten. Es handelt sich um ein völlig neues Design, das auf Geschwindigkeit optimiert ist und viel von unserem Code neu schreiben muss, für den dynamische Zuordnungen erforderlich sind. Für RDM 14.2 haben wir auch viele Subsysteme so überarbeitet, dass wir kein Speicherpooling mehr durchführen, um sicherzustellen, dass Speicher aus dem Systemstapel verwendet wird, oder APIs verwenden, bei denen das Objekt statisch in anderen Objekten zugeordnet ist. 

Die Hauptmerkmale des Speicherzuordners sind aus Sicht der obersten Ebene:

  1. Zuweisungen und Freigaben erfolgen mithilfe von Handles
  2. Der zugewiesene Speicher muss explizit freigegeben werden
  3. Die meisten Speicherzuweisungen und Freigaben erfolgen in der Reihenfolge der Ausführung O (1)
  4. Es gibt mehrere alternative Implementierungen
  5. Ein Master-Allokator verarbeitet die Zuweisungen von 4K-Seiten
  6. Unterzuweiser verarbeiten Zuweisungen, die kleiner als 2 KB sind
  7. Ein Stapelverteiler
  8. Systemstapel-Allokator

Alternative Implementierungen

Unsere Speicherzuordnungen verfügen über eine Reihe alternativer Implementierungen, die zur Kompilierungszeit ausgewählt werden können. Einige dieser Implementierungen unterscheiden sich in den Leistungsmerkmalen, während andere für Debugging- und QS-Zwecke verwendet werden.

Zum Beispiel haben wir eine Implementierung, die auf malloc und free basiert und mit Speicherprofil-Tools verwendet werden kann, um Probleme wie Pufferüberläufe, Speicherlecks und Thread-Probleme zu finden. Purify (Windows), Memcheck (Unix), Helgrind (Unix) und Efence (Unix) funktionieren alle mit dieser Implementierung. Wir haben auch eine Implementierung, die in unser Testframework für Speicherfehlersimulationen integriert ist. Schließlich gibt es auch eine Implementierung, mit der Zuordnungsgrößen profiliert werden können. Diese drei Implementierungen werden in diesem Dokument nicht weiter erläutert.

Verwendung von Griffen

Der neue Allokator verwendet ähnliche Handles wie der alte Allokator. Der große Unterschied besteht darin, dass der neue Allokator vollständig wiedereintrittsfähig ist. Der alte Allokator hatte ein ähnliches Konzept wie unser Sub-Allokator, aber es gab keine Master-Allokatoren. Der alte Allokator verwendete einen globalen Status, in dem die Einrichtung und das Herunterfahren einiger der verschiedenen Subsysteme unübersichtlich und nicht einfach zu überprüfen war. Der neue Allokator und eine Neugestaltung unserer Plattform-Support-Schicht (PSP) haben dies erheblich vereinfacht.

Aufgrund dieses neuen Allokator-Designs können jetzt zwei Instanzen von RDM in einen Prozess oder Adressraum eingebettet werden, ohne dass die Zuordnungen für eine die Zuordnungen der anderen beeinflussen. Beide Instanzen instanziieren ihren eigenen Master-Allokator, und diese Handles werden direkt oder indirekt für jede nachfolgende Zuordnung verwendet. Dies tun wir auch in unserem QS-Test-Framework. Ein Master-Allokator wird im Produkt verwendet, und ein anderer wird im QS-Test-Framework verwendet. Auf diese Weise können mögliche Speicherprobleme im QA-Testframework das zu testende Produkt nicht beeinträchtigen oder umgekehrt, und die Speicherprofilerstellung kann auch für Tests mit dem QA-Testframework durchgeführt werden.

Aus dem Master-Allokator können zwei Arten von Allokatoren abgerufen werden: der Unter-Allokator und der Stapel-Allokator. Diese Allokatoren geben auch Handles zurück, und ihre Implementierungen erhalten ihren Speicher vom Master-Allokator.

Einfädeln

Die neuen Speicherzuordnungen wurden unter Berücksichtigung des Threading entwickelt. Der Master-Allokator ist der einzige Allokator, der von mehreren Threads verwendet werden kann. Die Sub-Allokatoren verfügen nicht über einen integrierten Thread-Schutz. Jeder Sub-Allokator sollte normalerweise immer nur von einem Thread gleichzeitig verwendet werden. Es wird auch angenommen, dass Speicherzuweisungen und deren Verwendung für einen Thread lokal sind, um die Lokalität zu verbessern.

Eine Ausnahme ist, wenn ein Unterzuweiser Zuordnungen behandelt, die größer als 2 KB sind. In diesem Fall ist es sicher, dass es gleichzeitig zugewiesen und von mehreren Threads befreit wird, da diese Zuordnungen so ausgelegt sind, dass sie vom Master-Allokator verarbeitet werden.

Paging und Austauschen von Seiten auf die Festplatte

Bei Systemen mit virtuellem Speicher ist es wichtig zu vermeiden, dass Zuordnungen zufällig auf mehr Speicherseiten als erforderlich verteilt werden. Dies erfolgt, indem der Master-Allokator den Speicher in Seiten aufteilt, die genau auf 4 KB ausgerichtet sind. Der Master-Allokator speichert Metadaten zu den von ihm verwalteten Seiten separat. Auf diese Weise muss eine Seite, die freigegeben wird, nicht berührt werden. In dem Fall, in dem die Seite ausgelagert wurde, bleibt sie ausgelagert. Ein Sub-Allokator verwendet auch ausschließlich eine Reihe von Seiten. Es wird angenommen, dass dieser Ansatz dazu beiträgt, eine Überbeanspruchung des virtuellen Speichers zu vermeiden (wenn auch nur ein kleines bisschen).

Cache-Leistung

Der Master-Allokator richtet die Speicherzuordnungen auf 4 KB aus, und der Sub-Allokator kann Daten auf 64 Byte ausrichten (abhängig vom kompilierten Profil). Dies stellt sicher, dass Zuweisungen so wenige 64-Byte-Cache-Zeilen wie möglich kreuzen. Einige unserer Algorithmen basieren darauf, sodass wir höchstens einen Cache-Fehler garantieren können.

Minderung von Speicherlecks

Bei Speicherlecks werden im Debug-Modus Asserts im Code ausgelöst. Im Freigabemodus werden alle vom Master-Allokator abgeleiteten Zuordnungen freigegeben, wenn ein Sub-Allokator, ein Stapel-Allokator oder der Master-Allokator zerstört wird.

Der Master Allocator

Der oben beschriebene Master-Allokator ist für die Zuordnung der Seiten verantwortlich. Wenn mehrere Seiten zugewiesen wurden, werden zum Freigeben der Seiten nur das Handle für den Master-Allokator und ein Zeiger auf den Anfang des Speichers benötigt.

Der Master-Allokator fordert große Speicherblöcke vom Betriebssystem an. Jeder dieser großen Blöcke hat einen Header. Für jede 4K-Seite befindet sich im Header ein entsprechender Speicher, der zur Verwaltung der Seite verwendet wird. Wenn die Seite der Kopf oder das Ende einer Zuordnung oder eines freien Speicherbereichs ist, gibt es Informationen dazu sowie deren Größe. Diese Informationen werden beim Freigeben von Seiten verwendet, wo Speicherbereiche effizient zu größeren Bereichen kombiniert werden können. Die Invariante hierfür ist, dass niemals zwei freie Speicherbereiche nebeneinander liegen und dass der gesamte Speicher außerhalb des Headers entweder frei oder mit Informationen für jede Kopfseite und jeder Endseite für jede Zuordnung und jeden freien Bereich, der solche zeigt, zugewiesen ist . Alle anderen Seiten zwischen einem Kopf und einem Schwanz sind als kein Kopf oder Schwanz markiert.

Die entsprechende Information im Header bietet auch Platz für einen selbstausgleichenden binären Suchbaumknoten (AVL), mit dem eine AVL aller nach Größe sortierten freien Speicherbereiche verwaltet wird. Mit dieser AVL können wir eine passende Größe mit einer Reihenfolge von O (log n) finden, wobei n die Anzahl der freien Speicherbereiche ist. Da wir freien Speicher in Regionen kombinieren und immer die kleinste freie Region verwenden, die für eine Zuordnung geeignet ist, wird angenommen, dass n im Vergleich zur Anzahl der Seiten klein ist.

Das Zuweisen und Freigeben von Seiten verwendet nur Speicher im Header und wird daher als Cache- und insbesondere Paging-effizient angesehen. Wenn das System häufig Seiten zuweist und freigibt, ist der entsprechende Teil des Headers heiß und wird wahrscheinlich nicht aus dem CPU-Cache entfernt oder ausgelagert. Wenn das System jedoch in Bezug auf die Seitenzuweisungen statisch wird, werden diese Seiten möglicherweise aus dem CPU-Cache entfernt oder sogar ausgelagert.

Mit den oben genannten Überlegungen in seinem Design wird angenommen, dass unser Seitenzuweiser sehr effizient ist. Einige Anwendungsfälle können jedoch zu einer Fragmentierung führen. Es kann eine Idee sein, statischere Zuordnungen von dynamischeren zu trennen. Auf einem virtuellen Speichersystem, auf dem regelmäßig Paging durchgeführt wird, ist dies weniger bedenklich, da nur einige Seiten nicht verwendet werden und möglicherweise ausgelagert werden (und nie wieder ausgelagert werden).

Der Sub Allocator

Der oben beschriebene Unterzuweiser ist für das Zuweisen und Freigeben von Speicher für einen einzelnen Thread oder eine einzelne Aufgabe verantwortlich. Ein Sub-Allokator ist keinem Thread oder keiner Aufgabe direkt zugeordnet. Wir stellen jedoch sicher, dass separate Threads in RDM ihren eigenen Sub-Allokator verwenden.

Es gibt drei Haupttypen von Zuweisungen, die vom Unterzuweiser verarbeitet werden:

  1. Zuordnungen kleiner als ca. 2K
  2. Zuordnungen, die vom Master-Allokator verarbeitet werden können
  3. Zuordnungen, die an das Betriebssystem übergeben werden müssen

Das Hauptaugenmerk dieses Abschnitts liegt auf dem ersten Fall oben. Aber lassen Sie uns zuerst die beiden anderen Fälle kurz diskutieren. 

Zuordnungen, die vom Master-Zuweiser verarbeitet werden

Jeder Sub-Allokator wird, wenn er instanziiert wird, einem Master-Allokator zugeordnet. Wenn eine Zuordnung größer ist als das, was der Unterzuweiser selbst verarbeiten kann, kann sie an den Hauptzuweiser übergeben werden. Der Master-Allokator gibt eine Anzahl von 4K-Seiten zurück, die seitenausgerichtet sind. Da diese Zuordnungen immer an einer Seite ausgerichtet sind, weiß der Unterzuweiser auf diese Weise, dass diese Zuordnung vom Hauptzuweiser verarbeitet wurde, und wenn diese später freigegeben wird, kann sie direkt an den Hauptzuweiser übergeben werden.

Zuordnungen an das Betriebssystem übergeben

Wenn eine Zuordnung für den Master-Zuweiser zu groß ist (standardmäßig ca. 650 KB), wird die Zuordnung vom Betriebssystem übernommen. In diesem Fall ist ein spezieller Header reserviert. Wenn diese Zuordnung später freigegeben wird, weist der spezielle Header den Unterzuweiser an, sie direkt an das Betriebssystem zu übergeben.

Der Kernteil des Sub Allocators

Jetzt sind wir bereit, auf die Details des Sub-Allokators einzugehen. Zusätzlich zu dem, was wir zuvor erwähnt haben, gibt es drei Hauptimplementierungen. Die tatsächlich zu verwendende Implementierung kann zur Kompilierungszeit ausgewählt werden. Zunächst werden einige Merkmale erörtert, die allen drei Implementierungen gemeinsam sind.

Wie oben erwähnt, wird der Unterzuweiser von einem Hauptzuweiser instanziiert. Es werden mehrere Seiten vom Master-Allokator abgerufen. Eine Seite wird angefordert, wenn sie zum ersten Mal instanziiert wird. Jedes Mal, wenn eine Zuordnungsanforderung eingeht, die nicht in die bereits vorhandenen Seiten passt, wird eine zusätzliche Seite angefordert. Die vom Master-Allokator zugewiesenen Seiten werden niemals an den Master-Allokator zurückgegeben, es sei denn, der Sub-Allokator wird zerstört.

Der Kernteil des Sub-Allokators verarbeitet nur bestimmte Größen. Es gibt normalerweise zwei Größen für jede Zweierpotenz und die angeforderte Größe wird auf die nächste unterstützte Größe aufgerundet. Welche Größen genau unterstützt werden, hängt vom verwendeten Profil ab. Das standardmäßig kompilierte Profil ist für die Cache-Leistung optimiert. Dies bedeutet, dass keine Zuordnung mehr 64-Byte-Grenzen überschreitet als erforderlich.

Jede Seite, die vom Kernteil des Sub-Allokators verwaltet wird, ist für eine bestimmte Größe reserviert. Dies ermöglicht einen sehr geringen Overhead, da für jede einzelne Zuordnung kein Header benötigt wird. Wenn Speicher freigegeben wird, enthält der Seitenkopf alle Informationen, die zur effizienten Verwaltung des Speichers erforderlich sind.

Zuordnung fester Größen

Einige unserer Algorithmen führen kleine Zuordnungen fester Größe durch. Früher haben wir Speicherpools verwendet, aber wie sich herausstellte, ist unser neuer Allokator ungefähr so effizient wie die zuvor verwendeten Speicherpools. Durch das Inlining von Code mithilfe von Makros übertrifft unser neuer Speicherzuweiser die alte Implementierung mit dem Speicherpool. Die Verwendung des neuen Speicherzuordners hat auch den Vorteil, dass der Speicher nicht für einen bestimmten Zweck zugewiesen werden muss oder wie viel Speicher dafür reserviert werden muss.

Nachteile

Dieser Ansatz weist zwei Hauptnachteile auf.

Geben Sie zunächst für Anwendungen, die viele Speicherblöcke einer Größe zuweisen, diese frei und weisen Sie dann viele Speicherblöcke einer anderen Größe zu. Es wird angenommen, dass dies für RDM in bestimmten Anwendungsfällen bis zu einem gewissen Grad der Fall sein könnte, es wird jedoch angenommen, dass es den Nutzen dieses speziellen Ansatzes nicht überwiegt. Der beschriebene Ansatz ermöglicht sehr effiziente Algorithmen.

Zweitens bedeutet die Tatsache, dass jede Seite nur Zuordnungen einer bestimmten Größe verarbeitet, dass wir etwas Speicherplatz verschwenden. Auf lange Sicht, wenn durchschnittlich nur Zuordnungen unterschiedlicher Größe vorgenommen werden, werden 2 KB für jede unterstützte Größe verschwendet. Für das Standardprofil summiert sich dies auf 36 KB. Dies kann ein Problem für Anwendungen sein, die sehr wenig Speicher verwenden, aber kaum ein Problem für Anwendungen, die relativ viel Speicher verwenden.

Wir könnten auf jeder Seite unterschiedliche Größen zulassen, um die oben genannten Probleme zu beheben. Dies würde jedoch erfordern, dass mehr Informationen im Header gespeichert werden, und möglicherweise einen Header für jede Zuordnung. Dies würde auch den Speicherplatzaufwand erhöhen, und es wird angenommen, dass es sehr schwierig ist, einen Algorithmus zu entwickeln, der genauso effizient ist wie unser aktueller Allokator, zumal die Speicherplatznutzung und -leistung im Vergleich zum alten Allokator hervorragend sind.

Die drei Algorithmen

Drei alternative Algorithmen werden in den folgenden Unterabschnitten beschrieben.

Sub-Allokator, der eine Liste und eine Bitmap verwendet

Dieser Ansatz wird als der beste Ansatz in Bezug auf die Cache-Leistung angenommen. Lassen Sie uns untersuchen, wie es funktioniert.

Für jede unterstützte Seitengröße, auf der möglicherweise freier Speicherplatz vorhanden ist, wird eine Liste geführt. Wir sagen hier "könnte", weil wir beim Zuweisen von Speicher auf einer Seite nicht prüfen, ob wir den letzten freien Speicherplatz auf dieser Seite verwenden. Stattdessen entfernen wir die Seite später aus der Liste, wenn wir feststellen, dass wir diese Seite nicht zuordnen können. Dieser Ansatz ist etwas effizienter, als diese Prüfung immer durchzuführen und frühzeitig zu entfernen.

Jede Seite hat einen Header, der eine Bitmap enthält, die angibt, welcher Teil der Seite in Bezug auf die tatsächliche Größe, die diese Seite unterstützt, frei ist. Wir haben einen allgemeinen Algorithmus, um in dieser Bitmap nachzuschlagen, aber wir haben auch Implementierungen, die spezifisch für Plattformen sind, die Hardwareoptimierungen nutzen können.

Da dieser Algorithmus den freigegebenen Speicher nicht berührt, wird davon ausgegangen, dass dies für die Cache-Leistung am besten geeignet ist. Es ist jedoch Code erforderlich, der diesen Algorithmus verwendet, um den Speicher nicht zu berühren, wenn er den Speicher freigeben soll, um ihn voll auszunutzen. Einige frühe Profilerstellungen unseres Produkts haben mit dem letzten unten dargestellten Algorithmus eine bessere Leistung gezeigt.

Es wird auch angenommen, dass dieser Algorithmus für das Paging gut ist, da wir häufig Seiten zuweisen, auf die im Allgemeinen kürzlich zugegriffen wurde.

Sub-Allokator mit Liste der Listen

Dieser Algorithmus ähnelt dem vorherigen Algorithmus, außer dass wir eine Liste anstelle einer Bitmap innerhalb der Seite verwenden. Wir verwenden den Speicherplatz, der freigegeben wird, um einen Zeiger auf den nächsten freien Speicherort innerhalb der Seite zu halten. Es wird angenommen, dass dieser Algorithmus für die CPU-Cache-Leistung nicht optimal ist, er ist jedoch wahrscheinlich schneller, wenn die Bitmap keine Hardware-Unterstützung für die Suche bietet.

Es wird angenommen, dass dieser Algorithmus für das Paging genauso gut ist wie der erste Algorithmus.

Sub-Allokator mit einer einzigen Liste

Dies ähnelt dem vorherigen Algorithmus, außer dass wir für jede unterstützte Größe eine einzige Liste haben, die alle freien Speicherorte erreicht. Dieser Algorithmus scheint nach einigen frühen Profilen von RDM der effizienteste zu sein. Dies ist der verwendete Standardalgorithmus. Es wird angenommen, dass dies nicht die beste Leistung für die CPU-Cache-Leistung und die schlechteste Leistung für das Paging ist. Dieser Algorithmus schlägt wahrscheinlich die anderen Algorithmen aufgrund seiner Einfachheit. Dies ist jedoch möglicherweise nicht allgemein gültig. Wir vermuten, dass es aufgrund der CPU-Architektur oder -Anwendung Unterschiede geben kann. In Fällen, in denen erwartet wird, dass die Anwendung aufgrund übermäßiger Nutzung des virtuellen Speichers viel blättert, wird erwartet, dass dieser Algorithmus eine schlechtere Leistung erbringt.

Stapelverteiler

RDM verfügt über zwei Arten von Stapelzuweisern.

Einer von ihnen ist hauptsächlich für die Verwendung des Systemstapels ausgelegt. Zuweisungen erfolgen ohne Handle. Dieser Allokator sollte nur für Zuordnungen mit begrenzter Größe verwendet werden, und im Quellcode muss eine maximale Größe angegeben werden. Der genaue Ansatz, einschließlich der Frage, ob diese Zuordnungen tatsächlich den Systemstapel verwenden oder nicht, ist plattformabhängig.

Der andere Stapelzuweiser ist eine Implementierung, die den Unterzuweiser in ihrer Implementierung verwendet. Dieser Stapelzuweiser verwendet ein Handle ähnlich dem Unterzuweiser. Der Hauptvorteil dieser Art von Stapelzuweiser gegenüber dem Unterzuweiser besteht darin, dass die Verwaltung kleinerer Zuordnungen vermieden wird und ein Teil des Speichers freigegeben werden kann, indem etwas weiter unten auf dem Stapel freigegeben wird.