Statische Allocatie, Constant Werk

In reactie op de e-mail: Memory Safety’s Hardest Problem.

Er is een probleem waar ik eerder tegenaan ben gelopen, maar dat ik niet kon verwoorden. Jouw casus gaat over een pointer naar een variant in een union die overleeft nadat er een andere variant is weggeschreven; hierdoor lezen actieve, getypeerde pointers bytes die inmiddels tot iets anders behoren.

Vorig jaar schreef ik een limit-order matching engine en introduceerde ik per ongeluk een use-after-free: een geannuleerde order werd teruggegeven aan de pool terwijl deze nog gekoppeld was aan zijn prijsniveau. De volgende allocatie wees dat geheugen vervolgens toe aan een nieuwe order, waardoor de verouderde link bleef resolven. Ik had dit destijds gecategoriseerd als "ik was onvoorzichtig met lifetimes".

Na jouw bericht ben ik niet meer zeker of dat wel het geval was. Een recyclingpool lijkt op een tagged union waarbij de tag aangeeft "welke generatie objecten er momenteel in dit slot leeft", maar niets in het typesysteem houdt dit bij. Is dat een correcte interpretatie, of blijft het geval van de pool wezenlijk eenvoudiger omdat generatie-indexen dit daadwerkelijk oplossen en de union-casus geen equivalent heeft?

Geheugenveiligheid en Objectpools

Ja, objectpools zijn een interessant geval om over na te denken, omdat ze de relatie tussen geheugenveiligheid en algemene correctheid verduidelijken.

Overweeg eerst de situatie waarin geen objectpool wordt gebruikt, en we malloc en free gebruiken voor order-objecten. In dit geval verandert de logische fout van een use-after-free in fysieke type confusion (typeverwarring), wat gemakkelijk kan leiden tot het uitvoeren van willekeurige code. Als twee objecten van verschillende typen hetzelfde geheugenlocatie delen, kan een door de gebruiker gecontroleerd geheel getal in het ene object een functiepointer zijn in het andere: een exploiteerbaar goto-primitive.

Wat gebeurt er nu als we een objectpool introduceren die een lijst met "dode" objecten van type T opslaat? Een logische use-after-free is nog steeds mogelijk, maar het fysieke effect is nu anders. Er is nog steeds sprake van aliasing van het geheugen, maar er is geen type confusion. Je kunt niet zomaar een integer aanpassen om een functiepointer te wijzigen, tenzij je bovendien het lastige geval raakt waarbij het betreffende object een inline enum bevat. Uitgaande van het feit dat dit niet gebeurt, krijg je een perfect gedefinieerd, deterministisch gedrag, zelfs als je niet tevreden bent met het resultaat.

Dit suggereert een interessante oplossing voor het harden van code, die ik van Fil heb geleerd. Als je allocatiefunctie getypeerd is (hij neemt een T comptime-parameter of een runtime type witness, in plaats van een runtime type-erased grootte en uitlijning), dan kun je een allocator schrijven die intern gebruikmaakt van type-gesegregeerde pools.

Dit zal enigszins minder efficiënt zijn qua geheugengebruik, aangezien de allocator vrijgegeven geheugen van objecten van type U niet kan hergebruiken voor objecten van type T. De geheugenoverhead zal echter waarschijnlijk klein zijn (zeldzame objecttypes doen er niet toe, populaire types zullen veel hergebruik binnen hetzelfde type hebben). Je zou zelfs kunnen winnen in memory locality en de meeste vormen van type confusion oplossen.

Opnieuw: inline enums doorbreken dit, maar opmerkelijk genoeg werkt het weer als je enum-varianten altijd op de heap alloceert. Fil-C kan dit niet gebruiken omdat de interface van de C-allocator niet getypeerd is, maar iemand anders zou dat wel kunnen.

Maar dit is theoretisch. Hoe voorkomen we de bugs? Generatie-indexen zijn een populaire remedie, maar ik heb ze zelf nooit gebruikt, dus ik heb geen unieke inzichten in dit patroon. In plaats daarvan deel ik een paar andere trucs van TigerStyle. Ik heb slechts een vaag begrip van wat een order matching engine precies is, maar ik vermoed dat deze trucs daar kunnen helpen.

Statische Allocatie

De eerste truc is: geen dynamische geheugenallocatie na de initialisatie.

Dit is het idee van de pool, doorgetrokken naar zijn logische conclusie. We specificeren bij de opstart het maximale aantal orders waarmee we bereid zijn te werken, en we gaan daar nooit overheen. Je zou het programma bijvoorbeeld zo kunnen starten:

$ order-engine --orders-max=1000000

Een van de eerste regels in de main-functie zou dan zijn:

const orders: []Order = try gpa.alloc(Order, cliargs.ordersmax);

Als er tijdens runtime meer dan orders_max verzoeken binnenkomen, worden de overschrijdende verzoeken geweigerd. Iemand zou kunnen tegenwerpen: "Maar wat als ik eigenlijk nog wat reservegeheugen heb voor één extra order? Zou het niet een goed idee zijn om dat tenminste te proberen te behandelen?"

Mijn reactie zou zijn: "Nou, wat als je dat niet hebt?". Systemen die op volle capaciteit werken zonder strikte limieten, falen catastrofaal. Het proberen te alloceren van slechts één extra Order zou de OOM-killer van de kernel kunnen triggeren om de gehele order matching engine te beëindigen, waardoor de andere miljoen orders verloren gaan, of erger nog, het supervisor-proces doden zodat je het systeem niet eens meer kunt herstarten.

Statische allocatie geeft je gemoedsrust. Het systeem kan weigeren op te starten als er onvoldoende geheugen is, maar als het is opgestart, kun je er zeker van zijn dat het overbelasting gracieus afhandelt en de dienst blijft verlenen terwijl jij een krachtigere machine configureert.

Constant Werk

Wat doe je met de slice van orders? Een aanpak is om @memset(orders, undefined) te gebruiken en de slice over te dragen aan een pool die vrije objecten bijhoudt met een bitset:

const OrderPool = struct {
    orders: []Order,
    free: DynamicBitSet,
    fn acquire(pool: *OrderPool) ?*Order { ... }
    fn release(pool: *OrderPool, order: *Order) { ... }
};

Of met een free list:

const OrderPool = struct {
    orders: []union {
        order: Order,
        next_free: ?u32,
    },
    first_free: ?u32,
};

Er is echter een alternatieve benadering. In plaats van te denken aan een limiet op het aantal orders, kun je het systeem zo ontwerpen dat er altijd een vast aantal orders is, door een no-op (neutrale) order te introduceren:

const Order = {
    id: u128,
    price: u32,
    count: u32,
    tag: enum { bid, ask, reserved },
    pub const reserved: Order = .{
        .id = 0,
        .price = 0,
        .count = 0,
        .tag = .reserved,
    };
};

Je initialisatie wordt dan: @memset(orders, .reserved).

Een voordeel hiervan is cognitief: je denkt niet langer in termen van het creëren en vernietigen van orders. In plaats daarvan circuleren de orders simpelweg in het systeem volgens de wet van behoud van het aantal orders. Het wordt moeilijker om het overzicht over een order te verliezen als je altijd moet letten op niet alleen waar de order naartoe gaat, maar ook waar hij vandaan kwam. Je schrijft expliciet state-transitiefuncties voor elk paar toestanden, wat het makkelijker maakt om alle gevallen uitputtend op te sommen. En je controleert dit dubbel door op elk punt te asserten dat de staat is wat je verwacht (en vervolgens de asserts te verwijderen via DST).

Een ander voordeel is codevereenvoudiging en voorspelbaarheid. Je hoeft geen aparte collectie van "actieve" orders bij te houden. In plaats daarvan itereer je altijd over de volledige set en voer je no-ops uit voor de reserved orders. Dit voelt verspillend: zouden we de code niet sneller moeten laten draaien als er weinig orders zijn?

Maar overweeg dit: door vooraf de limiet van orders te specificeren, verbind je je ertoe dit aantal te kunnen bedienen. Als het maximale aantal orders actief is, heeft het systeem dan acceptabele prestaties? Zo niet, dan is dat een bug! Gray failure (waarbij het systeem onbruikbaar traag wordt) is een andere manier waarop een systeem kan breken bij het bereiken van de limiet.

Het vermijden van indexen verbetert de prestaties voor het geval van maximale belasting. Dit:

for (orders) |order| {
    process(order)
}

is veel eenvoudiger voor de compiler om te vectoriseren en voor de CPU-cache om te prefetchen dan dit:

for (orders_active) |order_index| {
    const order = orders[order_index];
    process(order);
}

Net als bij statische allocatie geeft het principe van Constant Work je gemoedsrust wat betreft prestaties. De P100-latentie blijft vlak, ongeacht de belasting. Onvoldoende prestaties worden ontdekt tijdens het uitrollen van het systeem, en niet tijdens de on-call dienst op Black Friday.

Bij TigerBeetle passen we dit patroon in het klein toe. In plaats van een zoeklus te schrijven met een early return:

const item = for (items) |item| {
    if (predicate(item)) break item;
} else null;

laten we de lus soms volledig uitlopen, waarbij we aanvullend asserten dat er een uniek matching item is: https://github.com/tigerbeetle/tigerbeetle/blob/0.17.9/src/vsr/grid.zig#L715-L725

Zoals gewoonlijk is dit een truc die nuttig is om in je arsenaal te hebben, maar het is geen universele oplossing voor alle programmeerproblemen.