java-topology/docs/tickets/mysql-0002-has-global-grant-fallback-linear-scan.md

mysql-0002 — has_global_grant: O(P) linear privilege scan in ACL-map fallback

Target: mysql/mysql-server Severity: MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) File: sql/auth/sql_security_ctx.cc Line: 737 Status: PATCHED

---

Defect

Security_context::has_global_grant(const char *, size_t) contains two paths for checking dynamic privileges:

1. Fast path (line 743–747): when m_acl_map != nullptr, uses unordered_map::find — O(1).
2. Slow path (line 735–740): when m_acl_map == nullptr (e.g. during bootstrap, after ACL reload, or in edge-case threaded scenarios), calls get_dynamic_privileges_map()->equal_range(key) then std::find(it, it_end, privilege) — O(P) linear scan over all privileges for this user in the multimap's equal range.

User_to_dynamic_privileges_map is std::unordered_multimap<Role_id, Grant_privilege> (defined in auth_internal.h:316). The equal_range returns all entries for the user (up to P items), and std::find walks them linearly comparing std::pair<string,bool> against the target privilege string.

The slow path is hit whenever the security context has not yet loaded its ACL map — this occurs on the first check per connection after a FLUSH PRIVILEGES or during multi-threaded plugin init. In a system with 200 dynamic privileges per user, every check in the slow path costs O(200) string comparisons.

Root Cause

The multimap fallback lacks a local hash index. After equal_range the code should use a temporary unordered_set or simply switch the inner storage for this user's privileges to a sorted vector so binary_search can be used.

Fix

Replace the std::find linear scan with a local unordered_set<std::string> built from the equal_range result, then do O(1) lookup. Or prefer std::find_if with early exit and add a comment explaining that callers should populate m_acl_map to avoid this path.

See: defects/mysql/patch/mysql-0002.patch

Benchmark

defects/mysql/unit/MysqlTest.java — has_global_grant fallback test case:

• Slow (linear equal_range scan): O(n) per check
• Fast (unordered_set): O(1) per check, speedup ≥ 20× at n=500