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.1 KiB
julia-0001: isrelocatable() scans Vector for membership per include → O(n²)
Target: JuliaLang/julia
Severity: MEDIUM
CWE: CWE-407 (Inefficient Algorithmic Complexity)
File: base/loading.jl — isrelocatable() (~line 2096)
Status: PATCHED
Description
isrelocatable() reads the cache header to retrieve includes (all included
files) and includes_srcfiles (the subset that are source files). It then
loops over includes and tests inc ∉ includes_srcfiles to identify
include-dependencies. includes_srcfiles is a Vector{CacheHeaderIncludes},
so ∉ compiles to a linear scan using == on each element. With n entries
in includes and up to n entries in includes_srcfiles, this is O(n²).
During package precompile validation, isrelocatable() is called for every
package in the depot. Large projects (hundreds of includes) pay quadratic cost
on every validation pass.
Root cause
# base/loading.jl ~2102
_, (includes, includes_srcfiles, _), _... = _parse_cache_header(io, path)
for inc in includes # outer O(n)
if inc ∉ includes_srcfiles # inner O(n) Vector linear scan
track_content = inc.mtime == -1.0
track_content || return false
end
end
includes_srcfiles is a Vector{CacheHeaderIncludes} built in
parse_cache_header. The ∉ operator on a Vector is O(length).
Fix
Build a Set{CacheHeaderIncludes} from includes_srcfiles before the loop so
membership tests are O(1).
srcfiles_set = Set{CacheHeaderIncludes}(includes_srcfiles)
for inc in includes
if inc ∉ srcfiles_set # O(1) hash lookup
track_content = inc.mtime == -1.0
track_content || return false
end
end
CacheHeaderIncludes is a mutable struct; equality (==) is already defined
structurally via isequal fallback, and hash can be derived from the
filename field (unique per include).
Ops numbers (Java benchmark)
See defects/julia/unit/JuliaTest.java (bench label "isrelocatable-includes").
At N=1000 includes: slow ~500,500 comparisons, fast ~1000 → ~500× speedup.