117 lines
3.6 KiB
Markdown
117 lines
3.6 KiB
Markdown
# UNDF: UNDF-2026-000000362
|
||
# chef-0001 — O(N²) run list dedup via Array#include?
|
||
|
||
**Severity:** MEDIUM
|
||
**Complexity:** O(N²) → O(N)
|
||
**CWE:** CWE-407 (Algorithmic Complexity)
|
||
|
||
## Affected Files
|
||
|
||
| File | Lines | Notes |
|
||
|------|-------|-------|
|
||
| `lib/chef/run_list.rb` | 65 | `RunList#<<`: dedup guard via Array#include? |
|
||
| `lib/chef/run_list/versioned_recipe_list.rb` | 39 | `VersionedRecipeList#add_recipe`: same pattern |
|
||
|
||
## Defective Code
|
||
|
||
### `lib/chef/run_list.rb` line 65
|
||
|
||
```ruby
|
||
def <<(run_list_item)
|
||
run_list_item = coerce_to_run_list_item(run_list_item)
|
||
@run_list_items << run_list_item unless @run_list_items.include?(run_list_item) # O(N) scan
|
||
self
|
||
end
|
||
```
|
||
|
||
### `lib/chef/run_list/versioned_recipe_list.rb` line 39
|
||
|
||
```ruby
|
||
def add_recipe(name, version = nil)
|
||
# ...version conflict check...
|
||
self << name unless include?(name) # include? delegates to Array#include? — O(N)
|
||
end
|
||
```
|
||
|
||
`VersionedRecipeList` inherits from `Array`. Its `include?` method is `Array#include?`,
|
||
which is an O(N) linear scan. `add_recipe` is called once per recipe during run list
|
||
expansion; for a run list of R recipes, total cost is O(R²).
|
||
|
||
## Why It Is O(N²)
|
||
|
||
`RunList#<<` is the append operator used to build `@run_list_items`. It guards against
|
||
duplicates with `@run_list_items.include?(run_list_item)`. `@run_list_items` is a plain
|
||
`Array`; `Array#include?` scans from index 0 to N−1 — O(N) per call.
|
||
|
||
Building a run list of N items via N `<<` calls costs:
|
||
- 1st call: scan 0 elements — O(0)
|
||
- 2nd call: scan 1 element — O(1)
|
||
- ...
|
||
- Nth call: scan N−1 elements — O(N−1)
|
||
|
||
Total: 0 + 1 + … + (N−1) = N(N−1)/2 = **O(N²)**.
|
||
|
||
`VersionedRecipeList#add_recipe` is the hot path during run list expansion: every role
|
||
expansion calls it for each recipe. A cookbook run involving R recipes across multiple
|
||
roles incurs R(R−1)/2 comparisons in total.
|
||
|
||
## Impact
|
||
|
||
A node with 500 recipes in its expanded run list (common in large Chef organizations
|
||
with many roles and nested roles) triggers ~125,000 string comparisons just for
|
||
deduplication. At 1000 recipes: ~500,000 comparisons. This adds measurable overhead to
|
||
every Chef client run during the compile phase.
|
||
|
||
## Fixed Code
|
||
|
||
### `lib/chef/run_list.rb` — add a shadow `Set` for O(1) membership tests
|
||
|
||
```ruby
|
||
def initialize(*run_list_items)
|
||
@run_list_items = []
|
||
@run_list_set = Set.new # shadow set for O(1) include? checks
|
||
run_list_items.map { |i| self << coerce_to_run_list_item(i) }
|
||
end
|
||
|
||
def <<(run_list_item)
|
||
run_list_item = coerce_to_run_list_item(run_list_item)
|
||
unless @run_list_set.include?(run_list_item)
|
||
@run_list_items << run_list_item
|
||
@run_list_set << run_list_item
|
||
end
|
||
self
|
||
end
|
||
```
|
||
|
||
### `lib/chef/run_list/versioned_recipe_list.rb` — replace Array with Set-backed dedup
|
||
|
||
```ruby
|
||
class VersionedRecipeList < Array
|
||
def initialize
|
||
super
|
||
@versions = {}
|
||
@seen_names = Set.new # O(1) membership instead of Array#include?
|
||
end
|
||
|
||
def add_recipe(name, version = nil)
|
||
if version && @versions.key?(name)
|
||
unless Chef::Version.new(@versions[name]) == Chef::Version.new(version)
|
||
raise Chef::Exceptions::CookbookVersionConflict, "..."
|
||
end
|
||
end
|
||
@versions[name] = version if version
|
||
unless @seen_names.include?(name)
|
||
@seen_names << name
|
||
self << name
|
||
end
|
||
end
|
||
end
|
||
```
|
||
|
||
Both fixes reduce duplication-checking from O(N²) to O(N) while preserving insertion order
|
||
(required for deterministic run list execution).
|
||
|
||
## Speedup
|
||
|
||
At N=500 unique recipes: ~125,000 comparisons (slow) vs ~500 comparisons (fast) → **≥250×**.
|
||
At N=1000: ~500,000 vs ~1000 → **≥500×**.
|