Efficient compiled binary policy format

[DemiMarie]

The problem you're addressing (if any)

The current qrexec policy format is inefficient. Determining whether a request is allowed requires potentially consulting every policy rule, which is O(n).

This is not a major problem now, as policies are rather small. However, in R4.1, the entire policy will be (effectively) a single file, which means that the parsing overhead will be much larger. Furthermore, other changes to qrexec have made it much more efficient, so the parsing overhead is a larger fraction of the total.

Describe the solution you'd like

There are several ways to speed up policy lookups:

• We can add a cache of recent policy evaluations.
• We can add indexes (similar to those used in a database) to avoid a linear scan of the entire policy.
• We can switch to a binary policy format, such as an SQLite database.

These approaches are not mutually exclusive, and not all need to be implemented. For example, a cache must be invalidated when necessary, while a binary policy format is much more difficult to audit.

Where is the value to a user, and who might that user be?

There are some applications, such as proxying web requests over qrexec, where qrexec calls are performance critical. This will help speed them up.

Describe alternatives you've considered

Additional context

This came up while thinking about #6264.

Relevant documentation you've consulted

Related, non-duplicate issues

[marmarek]

Currently the policy is loaded once (after a change) to a long living qrexec-policy-daemon. This avoids the most costly operation which is text file parsing. We can think of some further improvements if the current evaluation will be a bottleneck, but I think currently it isn't anymore.

[DemiMarie]

There are other improvements I can think of:

• Avoid spawning a qrexec-client process for each call.
• Handle all requests inside a single agent process, rather than forking a new process per connection.

[marmarek]

Since @DemiMarie opened yet another issue about the same thing, let me be clearer: not needed anytime soon. Actual policy evaluation (when it's already loaded and given "system info" structure) is a tiny fraction of qrexec call setup time. For example, fetching system info takes much more time. So, I'm closing it for now, we can re-consider it when it could actually provide a meaningful difference (and not before that).

[github-actions]

This issue has been closed as "declined." This means that the issue describes a legitimate bug (in the case of bug reports) or proposal (in the case of enhancements and tasks), and it is actionable, at least in principle. Nonetheless, it has been decided that no action will be taken on this issue. Here are some examples of reasons why an issue may be declined:

• No solution can be found.
• The proposed action is not possible.
• The proposed action would weaken security to an unacceptable degree.
• The proposed action would be too costly (in time, money, or other resources) relative to the benefits it would provide.
• The proposed action would make some things better while making other things worse, and the trade-off is not worthwhile.

These are just general examples. If the specific reason for this particular issue being declined has not already been provided, please feel free to leave a comment below asking for an explanation.

We respect the time and effort you have taken to file this issue, and we understand that this outcome may be unsatisfying. Please accept our sincere apologies and know that we greatly value your participation and membership in the Qubes community.

If anyone reading this believes that this issue was closed in error or that the resolution of "declined" is not accurate, please leave a comment below saying so, and the Qubes team will review this issue again. For more information, see How issues get closed.

[marmarek]

Example of a change that actually makes a difference, based on performance tests: #9362

[DemiMarie]

Since @DemiMarie opened yet another issue about the same thing, let me be clearer: not needed anytime soon. Actual policy evaluation (when it's already loaded and given "system info" structure) is a tiny fraction of qrexec call setup time. For example, fetching system info takes much more time. So, I'm closing it for now, we can re-consider it when it could actually provide a meaningful difference (and not before that).

Makes sense.

It’s worth noting that one can easily construct artificial benchmarks where policy evaluation is the bottleneck by simply adding a lot of rules. I’m more interested in performance in the real world.