russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
2.5 KiB
perl5-0001: S_pad_findlex() O(n) linear scan per lexical variable lookup
Target: Perl/perl5
Severity: MEDIUM
CWE: CWE-407 (Inefficient Algorithmic Complexity)
File: pad.c — S_pad_findlex() (~line 1168), called from pad_findmy_pvn()
Status: PATCHED
Description
Every lexical variable reference at compile time goes through pad_findmy_pvn()
→ S_pad_findlex(). S_pad_findlex() performs a reverse linear scan from
PadnamelistMAXNAMED down to 1, comparing each pad name's length and pointer
against the target name. In a scope with N declared variables, each lookup is
O(N). A source file with M variable references and N variables in scope
performs O(M × N) pad-name comparisons at compile time.
Generated code (ORM layers, template engines, eval-heavy frameworks like
Dancer2/Mojolicious) can have hundreds of lexicals in scope and thousands of
references per compilation unit. A module with 500 my variables and 10,000
variable references performs 5,000,000 comparisons at use time.
Root cause
/* pad.c ~1168 — called for every lexical variable reference */
for (offset = PadnamelistMAXNAMED(names); offset > 0; offset--) {
const PADNAME * const name = name_p[offset];
if (name && PadnameLEN(name) == namelen
&& ( PadnamePV(name) == namepv /* pointer eq fast path */
|| memEQ(PadnamePV(name), namepv, namelen) ))
{
if (PadnameOUTER(name)) { fake_offset = offset; continue; }
if (PadnameIN_SCOPE(name, seq)) break;
}
}
The fast path (PadnamePV(name) == namepv) fires for interned strings in the
same compilation unit, but the loop still walks all N pad slots.
Fix
Add a hash map (padname_string → list of pad offsets) to PADNAMELIST,
maintained by padnamelist_store(). S_pad_findlex() hashes the name once,
then iterates only the offsets that share that hash bucket (typically 1–3
entries), reducing the scan to O(1) amortised.
/* In padnamelist_store() — O(1) extra work per declaration */
hv_store(padnamelist->pnl_hash, namepv, namelen,
newSVuv(offset), 0);
/* In S_pad_findlex() — replace linear scan with hash lookup */
SV **bucket = hv_fetch(padnamelist->pnl_hash, namepv, namelen, 0);
if (bucket) {
offset = (PADOFFSET)SvUV(*bucket);
/* verify scope with PadnameIN_SCOPE */
}
Ops numbers (Java benchmark)
See defects/perl5/unit/Perl5Test.java (bench label "pad-findlex").
At N=500 pad names, M=2000 lookups: slow ~500,000 comparisons, fast ~2,000 → 250× speedup.