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
77 lines
2.9 KiB
Markdown
77 lines
2.9 KiB
Markdown
# envoy-0001: PreviousHostsRetryPredicate std::find O(n) per retry attempt → O(n²)
|
||
|
||
**Target:** envoyproxy/envoy
|
||
**Severity:** HIGH
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
**File:** `source/extensions/retry/host/previous_hosts/previous_hosts.h`
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
`PreviousHostsRetryPredicate::shouldSelectAnotherHost()` performs `std::find` on
|
||
`attempted_hosts_` (a `std::vector<HostDescription const*>`). This method is
|
||
called by the load balancer inside a host-selection retry loop
|
||
(`ZoneAwareLoadBalancerBase::chooseHost`) for every candidate host on every
|
||
retry attempt. With R retries and H previously-attempted hosts, the total work
|
||
is O(R × H) comparisons — O(n²) in the worst case where max_attempts equals
|
||
the cluster size.
|
||
|
||
| Location | Pattern |
|
||
|----------|---------|
|
||
| `previous_hosts.h:10` | `std::find(attempted_hosts_.begin(), attempted_hosts_.end(), &candidate_host)` |
|
||
| `load_balancer_impl.cc:668` | outer loop: `for (size_t i = 0; i < max_attempts; ++i)` calling `shouldSelectAnotherHost` |
|
||
| `thread_aware_lb_impl.cc:232` | same pattern in thread-aware variant |
|
||
|
||
## Root cause
|
||
|
||
```cpp
|
||
// previous_hosts.h — O(n) scan per call
|
||
bool shouldSelectAnotherHost(const Upstream::Host& candidate_host) override {
|
||
return std::find(attempted_hosts_.begin(), attempted_hosts_.end(),
|
||
&candidate_host) != attempted_hosts_.end();
|
||
}
|
||
void onHostAttempted(Upstream::HostDescriptionConstSharedPtr attempted_host) override {
|
||
attempted_hosts_.emplace_back(attempted_host.get());
|
||
}
|
||
private:
|
||
std::vector<Upstream::HostDescription const*> attempted_hosts_;
|
||
```
|
||
|
||
Caller loop in `load_balancer_impl.cc:658`:
|
||
```cpp
|
||
const size_t max_attempts = context ? context->hostSelectionRetryCount() + 1 : 1;
|
||
for (size_t i = 0; i < max_attempts; ++i) {
|
||
host = chooseHostOnce(context);
|
||
if (!host || !context || !context->shouldSelectAnotherHost(*host)) {
|
||
return host; // O(attempted_hosts) per iteration
|
||
}
|
||
}
|
||
```
|
||
|
||
With a cluster of N=100 endpoints and max_attempts=100, a single load-balancing
|
||
decision may require up to 100 × 100 = 10,000 pointer comparisons. In a busy
|
||
proxy handling thousands of requests/second, this compounds.
|
||
|
||
## Fix
|
||
|
||
Replace `attempted_hosts_` vector with `absl::flat_hash_set<>` or
|
||
`std::unordered_set<>`. Pointer identity is the key, so no custom hash is
|
||
needed — pointer addresses hash trivially.
|
||
|
||
```cpp
|
||
#include "absl/container/flat_hash_set.h"
|
||
|
||
bool shouldSelectAnotherHost(const Upstream::Host& candidate_host) override {
|
||
return attempted_hosts_.contains(&candidate_host); // O(1)
|
||
}
|
||
void onHostAttempted(Upstream::HostDescriptionConstSharedPtr attempted_host) override {
|
||
attempted_hosts_.insert(attempted_host.get()); // O(1) amortized
|
||
}
|
||
private:
|
||
absl::flat_hash_set<Upstream::HostDescription const*> attempted_hosts_;
|
||
```
|
||
|
||
## Ops/ns numbers (Java benchmark)
|
||
|
||
See `defects/envoy/unit/EnvoyTest.java`.
|
||
At R=100 retries, H=100 hosts: slow ~5050 ops, fast ~100 ops → >50× speedup.
|