russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
70 lines
2.9 KiB
ReStructuredText
70 lines
2.9 KiB
ReStructuredText
Yosys — CWE-407 Analysis
|
|
==========================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
Yosys is an open-source RTL synthesis framework used extensively in open-source FPGA
|
|
and ASIC flows. It performs logic optimization, technology mapping, and FSM extraction.
|
|
Its ``passes/cmds/scc`` pass implements Tarjan's SCC algorithm for combinational loop
|
|
detection. Its ``passes/opt/share`` pass performs cell-sharing optimization using DFS
|
|
traversal.
|
|
|
|
**Status: CLEAN — 0 confirmed defects**
|
|
|
|
Scanner returned 25 candidates; all are false positives on Yosys's ``pool<T>`` and
|
|
``dict<K,V>`` hash containers, which provide O(1) ``.count()``/``.insert()``.
|
|
|
|
Key Triage — SCC Pass
|
|
---------------------
|
|
|
|
The ``scc.cc`` Tarjan implementation is the highest-priority candidate. Full inspection
|
|
confirms it is **correct**::
|
|
|
|
pool<RTLIL::Cell*> workQueue; // hash set — O(1) erase/count
|
|
dict<RTLIL::Cell*, ...> cellLabels; // hash map — O(1) count/insert
|
|
pool<RTLIL::Cell*> cellsOnStack; // hash set — O(1) count/insert
|
|
std::vector<RTLIL::Cell*> cellStack; // ordered stack for pop — correct
|
|
|
|
// Tarjan DFS:
|
|
if (cellLabels.count(nextCell) == 0) // O(1) — dict lookup
|
|
if (cellsOnStack.count(nextCell) > 0) // O(1) — pool lookup
|
|
|
|
``pool<T>`` is Yosys's hash-backed set (similar to ``std::unordered_set``). ``dict<K,V>``
|
|
is Yosys's hash map. Both provide O(1) amortized membership. This is a textbook-correct
|
|
Tarjan implementation.
|
|
|
|
Container Pattern Triage
|
|
------------------------
|
|
|
|
All 25 scanner candidates follow the same pattern — ``.count()`` on a ``pool<T>`` or
|
|
``dict<K,V>`` inside a graph traversal loop:
|
|
|
|
- ``fsm_opt.cc`` — ``std::set<int>`` for unreachable state IDs — O(log n) ✓
|
|
- ``share.cc`` — ``pool<RTLIL::Cell*> stop`` in DFS cone search — O(1) ✓
|
|
- ``opt_expr.cc``, ``ltp.cc``, ``recover_names.cc``, ``abc.cc``, ``abc9.cc``,
|
|
``abc9_ops.cc``, ``sat/`` — all ``dict``/``pool`` — O(1) ✓
|
|
|
|
One candidate uses ``std::find`` on a ``std::vector``:
|
|
|
|
- ``glift.cc:341`` — ``std::find(ports.begin(), ports.end(), name)`` — O(|ports|)
|
|
**but** this is inside a ``log_assert()`` — assertion-only code that runs only in
|
|
debug builds; port lists are single-digit in size; not a CWE-407 defect.
|
|
|
|
Design Assessment
|
|
-----------------
|
|
|
|
Yosys uses its own ``pool<T>`` / ``dict<K,V>`` / ``idict<T>`` container library
|
|
(``kernel/hashlib.h``) throughout all graph algorithms. These are open-addressed hash
|
|
containers with O(1) amortized operations. The design team intentionally chose these
|
|
over ``std::set``/``std::map`` for performance. The codebase is effectively immune to
|
|
the CWE-407 membership pattern.
|
|
|
|
References
|
|
----------
|
|
|
|
* Scanner: ``tools/scans/yosys.sh``
|
|
* Scan result: ``tools/scan-results/yosys.txt`` — 25 candidates, all false positives
|
|
* Container library: ``kernel/hashlib.h`` — ``pool<T>``, ``dict<K,V>``, ``idict<T>``
|