UNDF: UNDF-2026-000000682

cockroachdb-0002: EnsureUserOnlyBelongsToRoles O(R²) slices.Contains in role sync loop

Severity

MEDIUM

Location

pkg/sql/authorization.go:570-572 — EnsureUserOnlyBelongsToRoles role membership diff loop

Pattern

SLOW: slices.Contains(roles, role) inside for role := range currentRoles loop — O(R) per iteration FAST: rolesSet := make(map[username.SQLUsername]struct{}, len(roles)) before loop — O(1) per iteration

Context

EnsureUserOnlyBelongsToRoles synchronizes a user's role memberships with an external source of truth (e.g. LDAP). It computes roles to revoke by iterating every current role and checking if it appears in the desired roles slice:

for role := range currentRoles {          // O(R_current) — map iteration
    if !slices.Contains(roles, role) {    // O(R_desired) — linear scan
        rolesToRevoke = append(rolesToRevoke, role)
    }
}

slices.Contains performs linear search over the roles slice. SQLUsername comparison is string equality on the internal .u field. With R_current=100 current roles and R_desired=100 desired roles (typical LDAP groups-per-user in large enterprises), this is O(10,000) string comparisons per sync operation. LDAP sync can run on every authentication or on a background schedule affecting all users.

The asymmetry is stark: the second loop (roles to grant) correctly uses currentRoles[role] map lookup at O(1). The first loop does not.

Speedup

100× at R=100 roles (enterprise LDAP with 100 group memberships per user)

Patch

--- a/pkg/sql/authorization.go
+++ b/pkg/sql/authorization.go
 func EnsureUserOnlyBelongsToRoles(...) error {
     return execCfg.InternalDB.DescsTxn(ctx, func(...) error {
         currentRoles, err := MemberOfWithAdminOption(ctx, execCfg, txn, user)
         if err != nil { return err }

         rolesToRevoke := make([]username.SQLUsername, 0, len(currentRoles))
         rolesToGrant  := make([]username.SQLUsername, 0, len(roles))
+        // Build O(1)-lookup set from the desired roles slice.
+        desiredRolesSet := make(map[username.SQLUsername]struct{}, len(roles))
+        for _, r := range roles {
+            desiredRolesSet[r] = struct{}{}
+        }
         for role := range currentRoles {
-            if !slices.Contains(roles, role) {
+            if _, ok := desiredRolesSet[role]; !ok {
                 rolesToRevoke = append(rolesToRevoke, role)
             }
         }
         for _, role := range roles {
             if _, ok := currentRoles[role]; !ok {
                 rolesToGrant = append(rolesToGrant, role)
             }
         }

The slices import can be removed from this file if this was the only usage (verify first).

2.7 KiB Raw Permalink Blame History Unescape Escape