XMPP: _dispatch herverwerkt hele deferred-backlog per nieuwe stanza — O(N²) in worst-case #1424

New issue

Closed

opened 2026-08-09 18:29:34 +00:00 by brenno · 0 comments

brenno commented

2026-08-09 18:29:34 +00:00

Owner

Bevinding

lib/xmpp/xmpp_transport.dart — _dispatch (regels 282–309) wordt bij elke nieuwe op/lock-stanza aangeroepen (_onOpStanza, _onLockStanza). Elke aanroep:

Kopieert de hele deferred backlog naar een lijst (regel 284: List<_DeferredStanza>.from(_deferred))
Wist de backlog (regel 285)
Bouwt een queue met backlog + fresh stanzas (regel 286–289)
Verwerkt de hele queue in een loop (regel 293–305)
Stanzas die nog niet open kunnen worden worden opnieuw toegevoegd aan _deferred (regel 300)

Worst-case complexiteit

Als er N deferred stanzas in de backlog staan die niet geopend kunnen worden (bijv. de afzender is onbekend, of de epoch-sleutel is nog niet aanwezig), en er komen M nieuwe stanzas binnen, dan:

Elke van de M nieuwe stanzas triggert een _dispatch-aanroep
Elke _dispatch verwerkt N + M stanzas
Totaal: O(M × (N + M)) = O(M×N + M²)

Met _maxDeferred = 256 (regel 170) is de worst-case O(M × 256) — elke nieuwe stanza triggert 256 mislukte open-pogingen (elk met een directory.resolve + eventuele crypto-operatie).

Waarom dit in de praktijk slaat

Dit treedt op als een deelnemer stanzas ontvangt van een afzender wiens device-keys nog niet zijn gepubliceerd of geïngest — bijv. een newcomer die net is gejoind en stanzas ontvangt vóór zijn keyshare. De backlog vult zich, en elke nieuwe stanza (ook van bekende afzenders) triggert een herverwerking van de hele backlog. In een drukke kamer met veel stanzas per seconde kan dit de CPU belasten.

Trust boundary

Interne logica — geen externe aanvaller, maar een drukke kamer met trage keying volstaat.

Impact

CPU-belasting in een drukke kamer met trage keying: elke nieuwe stanza triggert tot 256 mislukte open-pogingen.
De _maxDeferralRounds = 16 (regel 171) beperkt de duur (een stanza wordt na 16 ronden gedropt), maar niet de per-ronde kosten.
De backlog-kopie (regel 284) is ook een geheugen-alocatie per dispatch.

Oplossingsrichting

Verwerk alleen de fresh stanza, niet de hele backlog. In plaats van de backlog elke keer te kopiëren en te verwerken, verwerk alleen de nieuwe stanza. De backlog wordt apart verwerkt — bijv. door syncNow (die al elke seconde draait) of door een signaal als de key-state verandert (een nieuwe device-key ingest of een epoch-sleutel geïnstalleerd). Dit reduceert de per-stanza-kosten tot O(1) voor de fresh stanza.
Aanvullend: overweeg de backlog te verwerken alleen als de key-state daadwerkelijk is veranderd (een nieuwe ingest of installEpochKey), niet bij elke stanza. Dat is event-gedreven en elimineert de herverwerking volledig.
Aanvullend: als de backlog toch per-stanza wordt verwerkt, overweeg dan alleen de stanzas te herverwerken waarvan de afzender sinds de vorige ronde bekend is geworden — niet de hele backlog.

Locatie

lib/xmpp/xmpp_transport.dart regels 282–309 (_dispatch), 170–171 (_maxDeferred, _maxDeferralRounds)

Severity

MEDIUM — CPU-belasting in een drukke kamer met trage keying, beperkt door de caps maar O(N²) per definitie.

## Bevinding `lib/xmpp/xmpp_transport.dart` — `_dispatch` (regels 282–309) wordt bij elke nieuwe op/lock-stanza aangeroepen (`_onOpStanza`, `_onLockStanza`). Elke aanroep: 1. Kopieert de **hele** deferred backlog naar een lijst (regel 284: `List<_DeferredStanza>.from(_deferred)`) 2. Wist de backlog (regel 285) 3. Bouwt een queue met backlog + fresh stanzas (regel 286–289) 4. Verwerkt de hele queue in een loop (regel 293–305) 5. Stanzas die nog niet open kunnen worden worden opnieuw toegevoegd aan `_deferred` (regel 300) ### Worst-case complexiteit Als er N deferred stanzas in de backlog staan die niet geopend kunnen worden (bijv. de afzender is onbekend, of de epoch-sleutel is nog niet aanwezig), en er komen M nieuwe stanzas binnen, dan: - Elke van de M nieuwe stanzas triggert een `_dispatch`-aanroep - Elke `_dispatch` verwerkt N + M stanzas - Totaal: O(M × (N + M)) = O(M×N + M²) Met `_maxDeferred = 256` (regel 170) is de worst-case O(M × 256) — elke nieuwe stanza triggert 256 mislukte open-pogingen (elk met een `directory.resolve` + eventuele crypto-operatie). ### Waarom dit in de praktijk slaat Dit treedt op als een deelnemer stanzas ontvangt van een afzender wiens device-keys nog niet zijn gepubliceerd of geïngest — bijv. een newcomer die net is gejoind en stanzas ontvangt vóór zijn keyshare. De backlog vult zich, en elke nieuwe stanza (ook van bekende afzenders) triggert een herverwerking van de hele backlog. In een drukke kamer met veel stanzas per seconde kan dit de CPU belasten. ### Trust boundary Interne logica — geen externe aanvaller, maar een drukke kamer met trage keying volstaat. ### Impact - CPU-belasting in een drukke kamer met trage keying: elke nieuwe stanza triggert tot 256 mislukte open-pogingen. - De `_maxDeferralRounds = 16` (regel 171) beperkt de duur (een stanza wordt na 16 ronden gedropt), maar niet de per-ronde kosten. - De backlog-kopie (regel 284) is ook een geheugen-alocatie per dispatch. ### Oplossingsrichting 1. **Verwerk alleen de fresh stanza, niet de hele backlog.** In plaats van de backlog elke keer te kopiëren en te verwerken, verwerk alleen de nieuwe stanza. De backlog wordt apart verwerkt — bijv. door `syncNow` (die al elke seconde draait) of door een signaal als de key-state verandert (een nieuwe device-key ingest of een epoch-sleutel geïnstalleerd). Dit reduceert de per-stanza-kosten tot O(1) voor de fresh stanza. 2. **Aanvullend:** overweeg de backlog te verwerken alleen als de key-state daadwerkelijk is veranderd (een nieuwe `ingest` of `installEpochKey`), niet bij elke stanza. Dat is event-gedreven en elimineert de herverwerking volledig. 3. **Aanvullend:** als de backlog toch per-stanza wordt verwerkt, overweeg dan alleen de stanzas te herverwerken waarvan de afzender sinds de vorige ronde bekend is geworden — niet de hele backlog. ### Locatie - `lib/xmpp/xmpp_transport.dart` regels 282–309 (`_dispatch`), 170–171 (`_maxDeferred`, `_maxDeferralRounds`) ### Severity MEDIUM — CPU-belasting in een drukke kamer met trage keying, beperkt door de caps maar O(N²) per definitie.

brenno added the

enhancement

in-progress

labels

2026-08-09 18:29:34 +00:00

brenno referenced this issue

2026-08-09 20:47:29 +00:00

fix(xmpp): batch XMPP-bugfixes 1411-1434 #1438

brenno referenced this issue from a commit

2026-08-09 20:56:19 +00:00

fix(xmpp): sweep deferred backlog alleen bij key-change, niet elke stanza (#1424)

brenno