wave13: pyroscope-0001 UNDF-1301 (47x-438x GetBlockStats) + 5 clean-scan additions

Flagship: pyroscope PhlareDB.GetBlockStats slices.Contains per block
(O(B*U) -> O(B+U)). Long-retention tenants with 5k-10k blocks pay 1M+
membership checks per block-stats RPC. Set hoist: 438x at B=10k U=1k.

Wave 13 honor roll: lima, apollo-server, act, firecracker, nix.
Cumulative: 59 projects.

2026-04-25 14:30:18 -04:00

2.9 KiB

Raw Permalink Blame History

Pyroscope — CWE-407 Disclosure Brief

Project: Pyroscope (grafana/pyroscope) Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) MOAD: MOAD-2026-0001 A Sedimentary Defect Speedup: 438× measured at B=10k U=1k

Defect Map

What it is

Pyroscope's PhlareDB.GetBlockStats walks three block sets (heads, flushing, queriers) and for each block calls slices.Contains(req.Msg.GetUlids(), h.meta.ULID.String()) to check if the requested-ULID list contains it. slices.Contains is an O(U) linear scan. Total per-request cost: O(B × U) where B = total blocks across all sets, U = requested ULID count.

Long-retention tenants (Grafana Cloud Profiles, fleet-wide continuous profiling) accumulate thousands of block queriers. Operators issuing block-stats RPC with hundreds of ULIDs pay 1M+ membership checks per call. ULID.String() also re-formats the ULID to its canonical hex string per iteration, multiplying allocations.

Defect	UNDF
`pyroscope-0001`	undf-2026-000001301

Where it lives

pkg/phlaredb/phlaredb.go:597-613:

for _, h := range f.heads {
    if slices.Contains(req.Msg.GetUlids(), h.meta.ULID.String()) {
        res.BlockStats = append(res.BlockStats, h.GetMetaStats().ConvertToBlockStats())
    }
}
for _, h := range f.flushing { /* same */ }
for _, q := range f.blockQuerier.queriers { /* same */ }

Fix

Hoist req.Msg.GetUlids() into a map[string]struct{}{} once at the start of GetBlockStats. Per-iter cost drops from O(U) to O(1). Total cost: O(B + U).

requested := make(map[string]struct{}, len(req.Msg.GetUlids()))
for _, u := range req.Msg.GetUlids() {
    requested[u] = struct{}{}
}
for _, h := range f.heads {
    if _, ok := requested[h.meta.ULID.String()]; ok {
        res.BlockStats = append(res.BlockStats, h.GetMetaStats().ConvertToBlockStats())
    }
}

Bench (defects/pyroscope/bench/results.txt)

=== pyroscope-0001: PhlareDB.GetBlockStats O(B*U) -> O(B+U) ===

               scale    defective      fixed    speedup
-------------------------------------------------------
  B=  500 U= 100       1.81ms     0.04ms     47.0x
  B= 1000 U= 200       7.59ms     0.08ms     96.3x
  B= 2000 U= 200      15.66ms     0.15ms    103.0x
  B= 2000 U= 500      38.00ms     0.17ms    224.5x
  B= 5000 U= 500     102.96ms     0.36ms    282.2x
  B=10000 U=1000     239.79ms     0.55ms    438.8x

Why it matters

Continuous profiling at scale = thousands of blocks per tenant. Block-stats RPC sits on every UI inspect, every retention-pruning path, every cross-tenant aggregation. At B=10k U=1k, the patch drops a single GetBlockStats call from 240ms to 0.55ms — the difference between "profiling tab loads instantly" and "profiling tab freezes UI for a quarter second" on every refresh.

2.9 KiB Raw Permalink Blame History Unescape Escape