Der erste Teil dieser Artikelserie befasste sich mit einem für kleine Allokationen optimierten Pool-Allokator. Die Entwickler haben gesagt, dass sie viel in Qt tun, indem sie QEvent- oder QObject-Instanzen zuweisen, und ein spezialisierter Allokator kann auch für ihre Anwendungen nützlich sein. Bislang werden nach den Entscheidungen der Qt-Entwickler ganze Speicherseiten nach Bedarf allokiert und Datenblöcke einer festen Größe verteilt, die zur Kompilierzeit über einen Template-Parameter angegeben wird. Es unterstützt eine Vielzahl von Threading-Modellen mit unterschiedlichen Kompromissen in Bezug auf Leistung, Speichereffizienz und Parallelität. Die Entwickler erzielten sehr vielversprechende Ergebnisse und übertrafen Allzweckzuweisungen um das 3- bis 10-fache in Multithread-Tests.
Mit einem Allokator, der nur eine Blockgröße verarbeiten kann und niemals Speicher an das Betriebssystem zurückgibt, haben Entwickler jedoch noch einen weiten Weg vor sich, bevor sie die QEvent- und QObject-Nutzungsszenarien von Qt tatsächlich unterstützen können. Sie können nicht einfach eine Bibliothek verschwenden und Speicher belegen oder Anwendungsentwickler bitten, einen new/delete-Operator zu implementieren, um Instanzen ihrer großen Unterklassen zuweisen zu können.
Bevor Entwickler jedoch darüber nachdenken, wie sie mehr Komplexität hinzufügen können, müssen sie über das Testen nachdenken. In diesem Artikel wird es darum gehen.
Was wollen Entwickler testen?
Das Testen eines Zuordners nur unter Verwendung von Black-Box-Strategien ist sehr begrenzt. Entwickler können nicht sicher sein, dass ein Allokator korrekt arbeitet, indem sie nur auf die Zeiger schauen, die er empfängt. Sie möchten sicher sein, dass sich die Zuweisung im erwarteten Zustand befindet. Im Idealfall kann man dies tun, ohne Testcode schreiben zu müssen, der mehr oder weniger das dupliziert, was der Zuordner bereits tut. Im Grunde wird nur überprüft, ob Code kopiert/eingefügt werden kann (Code kopieren/einfügen). Außerdem müssten Sie, wenn Sie Zugriff auf interne Datenstrukturen hätten, diese beim Multithread-Testen blockieren, was Sie definitiv nicht wollen.
Aber auch bei einer fehlerfreien Implementierung des Allocators
der Benutzercode (Benutzercode) wird auch Fehler enthalten. Entwickler sollten vorhersehbare Fehler erhalten, wenn ihr Code illegale Lese- oder Schreibvorgänge durchführt, auf entfernte Objekte zugreift, Double-Free-Fehler oder Speicherlecks aufweist. Diese Speicherzugriffe verursachen normalerweise Segmentierungsverletzungsfehler mit einem nützlichen Stack-Trace. Aber Entwickler arbeiten nur mit dem Speicher, der zum Prozess gehört (es sei denn, wir stoßen an den Rand einer Speicherseite), und das Betriebssystem verfolgt nicht, was mit diesem Speicher passiert. Außerdem führt die Verwendung von benutzerdefinierten Allokatoren zu einem völlig neuen Fehlertyp, der Nichtübereinstimmung der Allokatoren. Alle Zuordner verwenden Datenstrukturen und Speicherlayouts, die für ihren effizienten Betrieb optimiert sind, sodass das Werfen einer beliebigen Adresse in einen Zuordner zu einem undefinierten Verhalten führt, wenn diese Adresse nicht von Anfang an von demselben Zuordner erhalten wurde.
Schließlich ist der Qt-Zuordner etwas konfigurierbar und für ziemlich spezifische Situationen ausgelegt. Entwickler möchten Daten darüber sammeln, wie die Zuweisung unter realen Bedingungen verwendet wird, damit sie Konfigurationen optimieren und sicherstellen können, dass es sich um den richtigen Zuweisungstyp handelt.
Bis die Entwickler wissen, dass der Allocator korrekt funktioniert, können sie die Fehlererkennung im Benutzercode beiseite lassen. Hier sind einige Dinge, die Sie überprüfen sollten, um die Implementierung sicher zu stellen:
• wenn so viele Fragmente zugewiesen werden, wie auf die Seite passen, und dann das erste zugewiesene Fragment freigegeben wird, dann sollte die nächste Auswahl keine zusätzliche Seite zuweisen;
• wenn mehr Datenfragmente zugewiesen werden, als auf die Seite passen, sollte der Zuordner eine neue Seite zuweisen;
• in einem Multi-Threaded-Zuordner werden benutzte Arenen nicht gelöscht, wenn der entsprechende Thread beendet wird, sondern als obsolet markiert;
• in einem Multithread-Zuordner wird der neue Thread die zuvor als veraltet markierte Arena wiederverwenden;
• In einer Multithread-Zuweisung teilen sich alle Threads dieselbe Arena.
Testen mit Richtlinie
Entwickler möchten den Allocator testbar machen, ohne ihn zu verlangsamen. Ein Zuordner, der Umgebungsvariablen oder andere Laufzeitkonfigurationen als Teil seiner Codepfade überprüfen muss, um beobachtbare Daten zu erhalten, muss zusätzliche Arbeit leisten, selbst wenn er nur prüft, ob der Funktionszeiger nullptr ist, bevor er aufgerufen wird. Entwickler möchten diesen Mehraufwand vermeiden. Es verlangsamt nicht nur die Dinge, sondern kann auch nicht offensichtliche Race-Bedingungen verbergen, die man möglicherweise in seinem Multithread-Code hat.
Glücklicherweise verwenden Entwickler C++ und implementieren den Allocator als Template-Klasse. Dies ermöglicht die Verwendung eines richtlinienbasierten Designs, bei dem eine Schnittstelle deklariert wird, über die der Zuordner wichtige Ereignisse melden kann, die bei seiner Implementierung auftreten:
enum class AnalyzerEvent {
Allocate,
Free,
ArenaCreate,
ArenaDestroy,
PageAllocate,
PageFree,
MemoryLeaked
};
// the no-op policy
struct NoAnalyzer
{
reportEvent(AnalyzerEvent, void *) {};
};
template<size_t ChunkSize, ThreadModel Threading = MultiThreaded,
typename Analyzer = NoAnalyzer>
class PoolAllocator : public Analyzer
{
// ...
struct Arena
{
Arena(PoolAllocator *allocator)
: m_allocator(allocator)
{
m_allocator->reportEvent(AnalyzerEvent::ArenaCreate, this);
}
// ...
bool grow()
{
void *ptr = ::mmap(NULL, sizeof(Page), PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
m_allocator->reportEvent(AnalyzerEvent::PageAllocate, ptr);
// ...
}
PoolAllocator *m_allocator;
};
public:
// ...
void *allocate(size_t size)
{
reportEvent(AnalyzerEvent::Allocate, &size);
// ...
}
void free(void *ptr)
{
reportEvent(AnalyzerEvent::Free, ptr);
// ...
}
};
Mit diesem Muster optimiert der Compiler standardmäßig einen leeren Funktionsaufruf. Und da die leere Basisoptimierung angewendet wird, erhöht sich die Größe der PoolAllocator-Instanz nicht. Es ist nicht einmal ein virtueller Funktionstisch erforderlich! Sie müssen einen Zeiger auf die Zuweisung zu den Arena-Instanzen übergeben, wo einige Ereignisse gemeldet werden, aber Sie werden später auch sehen, dass dieser Zeiger andere praktische Verwendungszwecke hat, also lohnt es sich, diese 8 Bytes pro Stream zu bezahlen.
Wenn eine Parser-Klasse bereitgestellt wird, kann Benutzercode direkt über die PoolAllocator-Instanz auf ihre Datenelemente zugreifen. Es muss darauf geachtet werden, dass keine Member deklariert werden, die mit vorhandenen Membern von PoolAllocator in Konflikt stehen, und der Parser muss außerdem Thread-sicher gemacht werden, wie für die PoolAllocator-Instanz konfiguriert. Dies führt normalerweise zu einem Mutex, sodass die Verwendung eines Parsers einige Auswirkungen auf das Verhalten und die Leistung des Zuordners hat, insbesondere in Umgebungen mit hoher Parallelität.
struct UsageAnalyzer
{
QBasicMutex m_mutex;
int pageCount = 0;
void recordEvent(AnalyzerEvent t, void *p)
{
std::lock_guard lock(m_mutex);
switch (t) {
case AnalyzerEvent::PageAllocate:
++pageCount;
break;
default:
break;
}
}
};
Mit einem solchen Parser können Sie Testfälle schreiben, die das korrekte Verhalten des Zuordners bestätigen, um beispielsweise die ersten beiden Elemente aus der obigen Liste zu überprüfen:
void tst_PoolAllocator::test()
{
PoolAllocator<16, SingleThreaded, UsageAnalyzer> allocator;
const size_t numChunks = allocator.chunksPerPage();
void *objects[numChunks];
QCOMPARE(allocator.pageCount, 0);
for (int i = 0; i < numChunks; ++i)
objects[i] = allocator.allocate(16);
QCOMPARE(allocator.pageCount, 1);
allocator.free(objects[0]);
objects[0] = allocator.allocate(16);
QCOMPARE(allocator.pageCount, 1);
void *object = allocator.allocate(16);
QCOMPARE(allocator.pageCount, 2);
allocator.free(object);
for (int i = 0; i < numChunks; ++i)
allocator.free(objects[i]);
}
Die Parser-Klasse kann erweitert werden, um die Gesamtnutzung der Zuweisung in der Anwendung zu verfolgen, und kann auch Speicherlecks melden, wenn die Zuweisung den Gültigkeitsbereich verlässt. Was noch nicht effizient getan wurde, ist die Zuordnung von beobachtbaren Metadaten zu einzelnen Zuordnern.
Metadaten mit Header
Der Qt-Allocator benötigt keinen Header für Zuordnungsinformationen, wenn wir die wenigen Zeiger ignorieren, die der Allocator selbst trägt – 99,8 % Speichernutzung. Jede 4K-Seite enthält einen Zeiger auf die Arena, zu der sie gehört, also gibt es 4088 Bytes an Datenblöcken. Das ist großartig, aber manchmal ist es nützlich, einige Metadaten mit jedem Allokator verknüpfen zu können. Beispielsweise möchten wir bestätigen, dass Zuweisungen mithilfe eines Poolzuordners tatsächlich nur von kurzer Dauer sind. Ein Anwendungsfall, bei dem solche Metadaten sogar Teil des Produktionssystems sein könnten, ist ein transparent implementierter Referenzzähler oder Garbage Collector.
Die bisher verwendete Datenstruktur für den Knotentyp war eine Vereinigung: für freie Knoten – ein Zeiger auf den vorherigen Knoten auf dem freien Stapel; für dedizierte Knoten - Array von Bytes:
union Node
{
Node *previous;
char chunk[ChunkSize];
};
Für die Standardfälle, in denen kein Header benötigt wird, bleiben wir bei diesem Layout. Wenn ein Header benötigt wird, muss ein weiteres Datenelement mit dem erforderlichen Platz hinzugefügt werden. Da der Pool-Allokator eine Vorlage ist, können Metaprogrammierungstechniken verwendet werden:
struct NoHeader {};
template<size_t ChunkSize, ThreadModel Threading = MultiThreaded,
typename Header = NoHeader, typename Analyzer = NoAnalyzer>
class PoolAllocator : public Analyzer
{
static constexpr size_t HeaderSize = std::is_empty<Header>::value
? 0 : sizeof(Header);
struct NodeDataWithHeader
{
char header[HeaderSize];
char chunk[ChunkSize];
};
struct NodeDataWithoutHeader
{
char chunk[ChunkSize];
};
using NodeData = typename std::conditional<HeaderSize == 0,
NodeDataWithoutHeader, NodeDataWithHeader>::type;
union Node
{
Node *previous;
NodeData data;
void initHeader()
{
if constexpr (HeaderSize > 0
&& std::is_default_constructible<Header>::value
&& !std::is_trivially_default_constructible<Header>::value) {
(void)new (node->header) Header();
}
}
void destructHeader()
{
if constexpr (HeaderSize > 0
&& std::is_destructible<Header>::value
&& !std::is_trivially_destructible<Header>::value) {
reinterpret_cast<Header*>(node->header)->~Header();
}
}
static Node *fromMemory(void *ptr)
{
return reinterpret_cast<Node*>(static_cast<char*>(ptr) - HeaderSize);
}
};
// ...
C++ erlaubt kein Array der Größe Null, und selbst wenn dies der Fall ist, verlangt der C++-Standard, dass jedes Mitglied einer Struktur eine eindeutige Adresse hat. Sogar ein Array der Größe Null verbraucht ein Byte Speicher, und sizeof gibt 1 für eine leere Struktur zurück. Um dieses Byte nicht zu verschwenden, wählen wir zur Kompilierzeit die entsprechende Struktur aus, je nachdem, ob der Typ leer ist oder nicht. Verwenden von C++17, wenn der constexpr-Operator Kompilierzeitfehler verhindert, wenn kein Header vorhanden ist, oder wenn der Header keine Erstellung oder Zerstörung erfordert. Die Hilfsfunktionen verbergen die Details, sodass allocate() und free() nicht viel komplizierter werden:
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
Node *node = arena()->pop();
if (!node)
return nullptr;
node->initHeader();
return node->data.chunk;
}
void free(void *ptr)
{
Node *node = Node::fromMemory(ptr);
node->destructHeader();
Arena *arena = Page::fromNode(node)->arena;
arena->push(node);
}
Da der Benutzercode etwas mit dem Header tun möchte, kann die Zuweisungsklasse Zugriff auf den Header für den Zeiger gewähren:
static Header *header(void *ptr)
{
if constexpr (HeaderSize == 0)
return nullptr;
return reinterpret_cast<Header*>(Node::fromMemory(ptr)->header);
}
};
Analyse
Jetzt ist es möglich, einige interessante Dinge mit Headern und Parsern zu tun. Da die Entwickler eine für kleine und kurzlebige Objekte optimierte Zuweisung erstellen, lassen Sie uns bestätigen, dass der Code tatsächlich Objekte zuweist:
struct TimingHeader
{
QElapsedTimer timer;
TimingHeader()
{
timer.start();
}
};
struct UsageAnalyzer
{
UsageAnalyzer(...)
{}
QBasicMutex m_mutex;
QMap<size_t, int> m_sizehistogram;
QMap<h;int, int> m_timeHistogram;
int m_pageCount = 0;
void recordEvent(QAllocator::AnalyzerEvent t, void *p);
};
// the biggest event we have seen in our last test was 112 bytes
using EventAllocator = PoolAllocator<112, MultiThreaded, TimingHeader, UsageAnalyzer>;
Q_GLOBAL_STATIC(EventAllocator, eventAllocator);
void UsageAnalyzer::recordEvent(AnalyzerEvent t, void *p)
{
std::lock_guard lock(m_mutex);
switch (t) {
case AnalyzerEvent::Allocate:
++m_sizeHistogram[*static_cast<size_t*>(p)];
break;
case AnalyzerEvent::Free:
++m_timeHistogram[QEventAllocator::header(p)->timer.elapsed()];
break;
case AnalyzerEvent::PageAllocate:
++m_pageCount;
break;
default:
break;
}
}
void *QEvent::operator new(std::size_t size) noexcept
{
qDebug() << "Usage:" << eventAllocator()->m_sizeHistogram;
return eventAllocator()->allocate(size);
}
void QEvent::operator delete(void *ptr) noexcept
{
qDebug() << "Timing:" << eventAllocator()->m_timeHistogram;
qDebug() << "Pages:" << eventAllocator()->m_pageCount;
eventAllocator()->free(ptr);
}
Wenn Sie dies in Qts qcoreevent.cpp verwenden und einen beliebigen Qt-Test ausführen, wird dies tatsächlich bestätigen, dass QEvent-Zuweisungen sowohl klein als auch sehr kurzlebig sind, mit sehr wenigen Ausnahmen.
Verwendung: QMap((24, 2367)(32, 26)(112, 557))
Timing: QMap((0, 44)(1, 10)(2, 91)(3, 116)(4, 330)(5, 524)(6, 546)(7, 397)(8, 338)( 9, 219)(10, 135)(11, 41)(12, 21)(13, 14)(14, 7)(15, 6)(30, 12)(31, 5)(32, 17)( 33, 3)(35, 7)(36, 10)(37, 3)(41, 11)(44, 5)(45, 7)(46, 2)(47, 4)(49, 1)( 63, 2)(90, 9)(95, 5)(96, 3)(215, 1)(19800, 2)(19802, 3))
Seiten: 4
Sie können auch sehen, dass der Höhepunkt bei 4 Seiten lag, die QEvent-Instanzen zugewiesen waren. 16K ist definitiv mehr als wir möchten, also muss dies definitiv optimiert werden.
Benutzercode debuggen
Jetzt, da wir sicherstellen können, dass der Allocator richtig implementiert ist und überhaupt der richtige Allocator verwendet wird, können wir uns darauf konzentrieren, es den Benutzern leichter zu machen, Fehler in ihrem Code zu erkennen.
Für den Anfang können Sie ein paar Trips in Debug-Builds hinzufügen. Dass der Zuordner wieder eine Vorlage ist, hilft, da nur der Code, der ihn verwendet, im Debug-Modus erstellt werden muss. Sie können beispielsweise eine einfache Double-Free-Erkennung hinzufügen, indem Sie den Stack durchlaufen und prüfen, ob sich der eingehende Knoten darauf befindet:
void push(Node *node)
{
#ifdef QT_DEBUG
Node *doubleFreeTest = stack;
while (doubleFreeTest) {
if (doubleFreeTest == node)
qFatal("Double free detected for %p", node->chunk);
doubleFreeTest = doubleFreeTest->previous;
}
#endif
node->previous = stack;
stack = node;
}
Es ist auch möglich, den freigegebenen Speicher eines Datenstücks mit Memset mit Müll zu füllen, um die Wahrscheinlichkeit zu erhöhen, dass die Verwendung eines solchen Speichers Fehler und undefiniertes Verhalten verursacht, das beim Debuggen leicht zu bemerken und zu identifizieren ist. Wenn Sie dies nur für Debug-Builds tun, wird dem Code, der in der Produktion ausgeführt wird, kein Overhead hinzugefügt.
Die Zuweisungsarchitektur von Qt ermöglicht auch einen wirksamen Schutz vor Zuweisungsfehlanpassungen. Da es einfach ist, die Adresse des Benutzers auf die Seite abzubilden, von dort auf Arena, und von dort dank des Zuweisungszeigers, der hinzugefügt werden musste, um die Richtlinienschnittstelle, den Zuordner, aufrufen zu können, konnte die Überprüfung erfolgen implementiert:
bool owns(void *memory) const
{
Page *page = Page::fromNode(Node::fromMemory(memory));
return page->arena->m_allocator == this;
}
void free(void *ptr)
{
if (!owns(ptr))
qFatal("Allocator mismatch for %p", ptr);
Node *node = Node::fromMemory(ptr);
node->destructHeader();
Arena *arena = Page::fromNode(node)->arena;
arena->push(node);
}
Es wäre hilfreich, wenn es mehrere Poolzuordner für unterschiedliche Größen oder Typen gäbe. Natürlich ist es wahrscheinlicher, dass es abstürzt, wenn free() oder owns() von einem völlig unbekannten Zeiger aufgerufen werden, in diesem Fall gibt es kein Problem.
Wenden Sie sich an den Sanitizer-Support
Ein sehr gutes und beliebtes Speicher-Debugging-Tool ist das Address Sanitizer-Tool. Compiler, die dies unterstützen, bieten APIs, mit denen Benutzercode Adressen und Speicherbereiche vergiften und dekomprimieren kann. Es gibt auch APIs, um zu überprüfen, ob Adressen und Speicherbereiche vergiftet sind, und dann können Sie sie verwenden, um zu überprüfen, ob das Vergiften und Entfernen von Bereichen korrekt ist. Die Verwendung der ASan-APIs verbessert implizit auch das Testen des Zuweisungscodes selbst, da wir vergiftete Adressen ansprechen werden, wenn beispielsweise die Zeigerarithmetik korrekt ist.
Im Codeüberprüfungsabschnitt wird die ASan-Unterstützung als separates Commit hinzugefügt.
