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
54 lines
1.7 KiB
Markdown
54 lines
1.7 KiB
Markdown
# allegro5-0001 — al_play_sample O(n) linear scan of sample pool per play call
|
|
|
|
## Status
|
|
PATCHED
|
|
|
|
## Severity
|
|
MEDIUM
|
|
|
|
## Target
|
|
allegro5 `addons/audio/kcm_sample.c`
|
|
|
|
## CWE
|
|
CWE-407: Algorithmic Complexity — Insufficient Complexity Reduction Before Algorithmic
|
|
Intensive Operation
|
|
|
|
## Description
|
|
`al_play_sample()` performs an O(n) linear scan of the `auto_samples` pool to find the
|
|
first free (not playing, not locked) slot. The pool is sized by `al_reserve_samples(n)`.
|
|
|
|
```c
|
|
// kcm_sample.c:355
|
|
bool al_play_sample(ALLEGRO_SAMPLE *spl, float gain, float pan, float speed,
|
|
ALLEGRO_PLAYMODE loop, ALLEGRO_SAMPLE_ID *ret_id)
|
|
{
|
|
for (i = 0; i < _al_vector_size(&auto_samples); i++) { // O(n) per play
|
|
AUTO_SAMPLE *slot = _al_vector_ref(&auto_samples, i);
|
|
if (!al_get_sample_instance_playing(slot->instance) && !slot->locked) {
|
|
...
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
```
|
|
|
|
In typical game code calling `al_play_sample()` for every sound effect (footsteps,
|
|
gunshots, explosions) on each frame, with a pool of N reserved samples, each call
|
|
scans O(N) instances. With P play calls per frame the total cost is O(P * N).
|
|
|
|
## Fix
|
|
Maintain a `free_head` index or a separate queue/stack of free slot indices.
|
|
On slot release (sample finishes playing), push the index onto the free stack.
|
|
`al_play_sample` pops the free stack: O(1) amortized.
|
|
|
|
The existing `ALLEGRO_SAMPLE_ID` with `_index` already stores the slot index —
|
|
the infrastructure is in place to track free slots separately.
|
|
|
|
## Complexity
|
|
- Before: O(n) per al_play_sample call where n = al_reserve_samples count
|
|
- After: O(1) amortized with free-slot stack
|
|
|
|
## Files
|
|
- `defects/allegro5/patch/allegro5-0001.patch`
|
|
- `defects/allegro5/unit/Allegro5SamplePoolTest.java`
|