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

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

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

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

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×.

3.6 KiB Raw Permalink Blame History Unescape Escape