java-topology/defects/frrouting/patch/frrouting-0003-community-uniq-sort-dedup.md

UNDF: UNDF-2026-000000401

frrouting-0003: community_uniq_sort O(N²) → O(N log N) sort+dedup

Classification

Field	Value
CWE	CWE-407 Inefficient Algorithmic Complexity
Severity	HIGH
Component	bgpd/bgp_community.c:143
Function	community_uniq_sort
Hot path	Per-BGP-UPDATE parse + per-route route-map apply + aggregate recompute
Status	PATCHED (unit test PASS)

Defect

community_uniq_sort builds a deduplicated sorted community list. For each of N input entries it calls community_include(new, val) which is an O(N) linear scan of the already-built output array:

// bgp_community.c:143
struct community *community_uniq_sort(struct community *com) {
    ...
    for (int i = 0; i < com->size; i++) {
        uint32_t val = community_val_get(com, i);
        if (!community_include(new, val)) {   // O(N) scan of new->val
            community_add_val(new, val);
        }
    }
    qsort(new->val, new->size, COMMUNITY_SIZE, community_val_cmp);
    return new;
}

Total: O(N²) dedup + O(N log N) sort. The qsort at the end is correct but wasted on an already-sorted result if we sort-first.

Invocation sites (all per-route hot paths):

1. bgp_community.c:504 — community_parse() — every incoming BGP UPDATE
2. bgp_routemap.c:2849 — route_set_community_apply() additive merge
3. bgp_community.c:983 — bgp_compute_aggregate_community() aggregate rebuild
4. bgp_mpath.c:676 — multipath best-path community merge

Fix

Sort all N entries first (O(N log N)), then do a single O(N) linear dedup pass:

struct community *community_uniq_sort(struct community *com) {
    struct community *new = community_new();
    // Copy all entries
    for (int i = 0; i < com->size; i++)
        community_add_val(new, community_val_get(com, i));
    // Sort once: O(N log N)
    qsort(new->val, new->size, COMMUNITY_SIZE, community_val_cmp);
    // Linear dedup: O(N)
    int out = 0;
    for (int i = 0; i < new->size; i++) {
        if (i == 0 || community_val_get(new, i) != community_val_get(new, i - 1))
            community_set_val(new, out++, community_val_get(new, i));
    }
    new->size = out;
    return new;
}

Speedup: ~250× at N=500 (replaces O(N²)=250K with O(N log N)≈4.5K comparisons).