java-topology/docs/tickets/unrealircd-0002-sjoin-find-membership-link-quadratic.md

unrealircd-0002: SJOIN member loop calls find_membership_link() O(M×C)

Target: unrealircd/unrealircd Severity: MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) File: src/modules/sjoin.c:292 Status: PATCHED

Description

During SJOIN timestamp collision resolution (the server that loses drops all its channel modes), UnrealIRCd iterates over all channel members (channel->members) and for each one calls find_membership_link(lp->client->user->channel, channel) to obtain the client's Membership struct for that channel.

find_membership_link is an O(C) linear walk of the client's channel linked list (channel.c:100–113).

Result: O(M × C) per SJOIN collision where M = members in channel, C = channels per client (up to the join limit, typically 50).

Root cause

// sjoin.c:292
for (lp = channel->members; lp; lp = lp->next)
{
    // O(C) — walks client's full channel membership list to find this channel
    Membership *lp2 = find_membership_link(lp->client->user->channel, channel);
    ...
    *lp->member_modes = *lp2->member_modes = '\0';
}

The Membership struct lp2 is being fetched so that both the channel-side and the client-side member_modes can be zeroed simultaneously. However, lp->client->user->channel gives the head of the client's membership list, and we already have lp (the channel's Member struct) in hand. The client-side Membership can be located in O(1) from the Member pointer via the dual-link structure (Member → Client → Membership list), or by embedding a back-pointer.

Fix

The Member struct already has lp->client. The corresponding Membership struct on the client side can be found without a list scan if a back-pointer or a parallel data structure is maintained. Alternatively, zero both fields directly from lp since the Member and Membership structs for the same (client, channel) pair share the same member_modes by design:

for (lp = channel->members; lp; lp = lp->next)
{
    // Instead of find_membership_link, zero the mode buffer directly.
    // If client-side Membership also needs zeroing, add a direct backpointer
    // in the Member struct pointing to the corresponding Membership entry.
    for (p = lp->member_modes; *p; p++) Addit(*p, lp->client->name);
    *lp->member_modes = '\0';
    // lp2 only needed for *lp2->member_modes = '\0'; — cache via backptr
}

Ops/ns numbers (Java benchmark)

See defects/unrealircd/unit/UnrealircdTest.java (included in scenario 3). At M=500 members, C=50 channels/client: slow ~25,000 ops, fast ~500 ops → ~50× speedup.