# UNDF: UNDF-2026-000000406
# grafana-0002: Folder/dashboard permission UID deduplication O(P²)

**CWE:** CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
**Severity:** MEDIUM
**Component:** `pkg/services/folder/folderimpl/folder.go`,
               `pkg/services/dashboards/service/dashboard_service.go`
**Commit:** 60dd922a

## Defect

Four permission deduplication loops use `slices.Contains` on a growing slice inside a
`for _, p := range folderPermissions` loop.  Each `slices.Contains` call scans the
already-accumulated slice, giving O(P²) over the entire loop where P = permission count.

### folder.go — three sites

**Site 1 — GetChildren (line 253):**
```go
// folder.go:245-256
for _, p := range folderPermissions {               // O(P) outer
    if folderUid, found := strings.CutPrefix(p, dashboards.ScopeFoldersPrefix); found {
        if !slices.Contains(qry.AncestorUIDs, folderUid) {  // O(P) scan growing slice
            qry.AncestorUIDs = append(qry.AncestorUIDs, folderUid)
        }
    }
}
```

**Site 2 — GetChildren (line 451):**
```go
// folder.go:443-455
for _, p := range folderPermissions {               // O(P) outer
    if folderUid, found := strings.CutPrefix(p, dashboards.ScopeFoldersPrefix); found {
        if !slices.Contains(q.FolderUIDs, folderUid) {      // O(P) scan growing slice
            q.FolderUIDs = append(q.FolderUIDs, folderUid)
        }
    }
}
```

**Site 3 — getFoldersForUser (line 544):**
```go
// folder.go:542-548
for _, p := range folderPermissions {               // O(P) outer
    if folderUid, found := strings.CutPrefix(p, dashboards.ScopeFoldersPrefix); found {
        if !slices.Contains(folderUids, folderUid) {        // O(P) scan growing slice
            folderUids = append(folderUids, folderUid)
        }
    }
}
```

### dashboard_service.go — one site

**Site 4 — getDashboardsSharedWithUser (line 1534):**
```go
// dashboard_service.go:1532-1538
for _, p := range dashboardPermissions {            // O(P) outer
    if dashboardUid, found := strings.CutPrefix(p, dashboards.ScopeDashboardsPrefix); found {
        if !slices.Contains(dashboardUids, dashboardUid) {  // O(P) scan growing slice
            dashboardUids = append(dashboardUids, dashboardUid)
        }
    }
}
```

## Impact

`GetPermissions()` returns one scope-string per ACL entry.  In a Grafana installation
with many shared folders (enterprise teams, nested folder hierarchies) a user can
accumulate hundreds of permission entries.  Each of these four paths is called on
every API request that lists folders or dashboards for a user.  At P=500 permissions,
each call costs 500×500/2 = **125,000** comparisons instead of 500.

## Fix

Replace the growing-slice dedup with a `map[string]struct{}` seen-set, then collect
keys at the end:

```go
// Pattern for all four sites:
seenUIDs := make(map[string]struct{}, len(folderPermissions))
var uids []string
for _, p := range folderPermissions {
    if uid, found := strings.CutPrefix(p, dashboards.ScopeFoldersPrefix); found {
        if _, ok := seenUIDs[uid]; !ok {
            seenUIDs[uid] = struct{}{}
            uids = append(uids, uid)
        }
    }
}
// assign uids to qry.AncestorUIDs / q.FolderUIDs / folderUids / dashboardUids
```

## Complexity

| Version  | Per-request dedup cost | P=500 ops |
|----------|------------------------|-----------|
| Defective | O(P²)                  | 125,000   |
| Patched   | O(P)                   | 500       |
| Speedup   |                        | **250×**  |
