Profiling rego - rule reevaluation when returning data from it

[AdrianArnautu]

Hi folks,

I was profiling our rego and I've noticed that our rules are evaluated multiple times, unexpected to me.
I need help to understand if the numbers are correct and if I can improve them.

This is the data.json, one role can have permissions to multiple resources

{
  "static": {
    "role_data": {
      "role3": {
        "permissions": {
          "resource1": {
            "read": true,
            "write": true
          }
        }
      },
      "role10": {
        "permissions": {
          "resource1": {
            "read": true,
            "write": true
          }
        }
      },
      "role11": {
        "permissions": {
          "resource1": {
            "read": true,
            "write": true
          }
        }
      },
      "role12": {
        "permissions": {
          "resource1": {
            "read": true,
            "write": true
          }
        }
      }
    }
  }
}

And two policies:

main.rego

package main

import data.subject

allows[policy_name] {
        subject.rbac_allowed
        policy_name := "rbac"
}

default allow = false

allow {
        allows[_]
}

subject.rego

package subject

matched_roles[role] {
        role := input.subject.roles[_]
        data.static.role_data[role.id].permissions[input.resource.type][input.resource.action]
}

rbac_allowed {
        count(matched_roles) != 0
}

We return the matched roles as we need the result in a different rule that is missed here on purpose.

The input is (some parts are missed on purpose)

{
    "resource": {
      "action": "read",
      "type": "resource1"
    },
    "subject": {
      "roles": [
        {"id": "role3"},
        {"id": "role10"},
        {"id": "role11"},
        {"id": "role12"}
      ]
    }
}

The logic is: we provide the user assignments on input, the action and the resource type and OPA evaluates the RBAC policy, i.e if the user can do that action on the given resource having the provided assignments

We profile the policies with
./opa eval --bundle /bundle --fail --explain full --profile --profile-sort num_redo --profile-limit 100 --format=pretty --input input.json 'data.main.allow'

And we get back

+----------+----------+----------+----------------------------------+
|   TIME   | NUM EVAL | NUM REDO |            LOCATION             |
+----------+----------+----------+----------------------------------+
| 151.83µs | 16       | 16       | /bundle/resources/subject.rego:5 |
| 28.208µs | 1        | 4        | /bundle/resources/subject.rego:4 |
| 44.248µs | 3        | 3        | /bundle/resources/subject.rego:9 |
| 18.167µs | 1        | 1        | data.main.allow                        |
| 15.583µs | 1        | 1        | /bundle/resources/main.rego:13   |
| 9.084µs  | 1        | 1        | /bundle/resources/main.rego:6    |
| 8.833µs  | 1        | 1        | /bundle/resources/main.rego:7    |
+----------+----------+----------+----------------------------------+```

The 16 evaluations of data.static.role_data[role.id].permissions[input.resource.type][input.resource.action] line is not understood by me. Help? :)

If I change the subject.rego to just evaluate the matched roles and not return them

matched_roles {
        role := input.subject.roles[_]
        data.static.role_data[role.id].permissions[input.resource.type][input.resource.action]
}

I get the expected 4 evaluations:

+----------+----------+----------+--------------------------------+
|   TIME   | NUM EVAL | NUM REDO |           LOCATION  |
+----------+----------+----------+--------------------------------+
| 48.71µs  | 4        | 4        | /bundle/resources/subject.rego:5 |
| 25.501µs | 1        | 1        | /bundle/resources/subject.rego:4 |
| 23.75µs  | 1        | 1        | data.main.allow                      |
| 16.625µs | 1        | 1        | /bundle/resources/main.rego:13   |
| 11.834µs | 1        | 1        | /bundle/resources/subject.rego:9 |
| 7.708µs  | 1        | 1        | /bundle/resources/main.rego:6    |
| 7.041µs  | 1        | 1        | /bundle/resources/main.rego:7    |
+----------+----------+----------+-------------------+

Version: 0.50.2
Build Commit: 0ffef53acc0a4f4063b4155a2c54cb6f3c349139
Build Timestamp: 2023-03-21T11:36:06Z
Build Hostname: Mac-1679398659007.local
Go Version: go1.20.2
Platform: darwin/arm64

[srenatus]

Excuse the brief answer, but a common pitfall is that

data.static.role_data[role.id].permissions[input.resource.type][input.resource.action]

really is expanded to something like these four expressions

a = role.id
b = input.resource.type
c = input.resource.action
data.static.role_data[a].permissions[b][c]

and when the profiling is done, the counts of EVAL/REDO for each of these expressions are added up. This easily misleads.

[AdrianArnautu]

@srenatus thank you, it makes sense.
Using print function I can see when the rule is not returning the result it's lazy in nature - evaluation stops when the first entry matches.

One way I can reduce the numbers is by flattening the data as the time fetching it depends greatly on the number of nested levels I've pinned it down to these lines https://github.com/open-policy-agent/opa/blob/main/storage/internal/ptr/ptr.go#L17

But going too far, I get recursion err, any idea why?
Expected behaviour and the rule has to be rewritten or a bug?

1 error occurred: bundle/resources/subject.rego:3: rego_recursion_error: rule data.subject.matched_roles is recursive: data.subject.matched_roles -> data.subject.matched_roles

data.json

{                                                                                                                                                                                                                                                                     
      "role3": {
          "resource1": {
            "read": true,
            "write": true
          }
      },
      "role10": {
          "resource1": {
            "read": true,
            "write": true
          }
      },
      "role11": {
          "resource1": {
            "read": true,
            "write": true
          }
      },
      "role12": {
          "resource1": {
            "read": true,
            "write": true
          }
      }
}

rego:

package subject                                                                                                                                                                                                                                                       

matched_roles[role] {
        role := input.subject.roles[_]
        data[role.id][input.resource.type][input.resource.action]
}

[srenatus]

Short fix: put your data under data.mapping or data.roles when you define your package as data.subject.

Long answer: the compiler needs to be very cautious to avoid recursion. In the odd case that your input is

subject:
  roles:
  - id: subject
resource:
  type: matched_roles

then matched_roles would try to evaluate data["subject"]["matched_roles"] -- and that may not happen. If you put your data into some other subtree, and have the prefix in that last line of matched_roles, that cannot happen for any possible input.

[AdrianArnautu]

Thank you @srenatus , I've got my answers, I'm closing this one.