]> git.proxmox.com Git - pve-access-control.git/commit - src/PVE/AccessControl.pm
fix #4518: improve ACL computation performance
authorFabian Grünbichler <f.gruenbichler@proxmox.com>
Wed, 15 Feb 2023 09:44:13 +0000 (10:44 +0100)
committerThomas Lamprecht <t.lamprecht@proxmox.com>
Mon, 6 Mar 2023 09:37:51 +0000 (10:37 +0100)
commit170cf17bf791b4373540102b1e58bcb61d716fd6
treeb8e00f84bfb2d2cdb076ce1a0094e7d6aa9598ae
parent25fb12c4cbb34a4ea9a18c0a15d3d8f196794e62
fix #4518: improve ACL computation performance

by switching to a tree-based in-memory structure, like we do in PBS.

instead of parsing ACL entries into a hash using the full ACL path as key for
each entry, parse them into a tree-like nested hash. when evaluating ACLs,
iterating over all path prefixes starting at '/' is needed anyway, so this is a
more natural way to store and access the parsed configuration.

some performance data, timing `pveum user permissions $user > /dev/null` for
various amounts of ACL entries in user.cfg

entries | stock  | patched  | speedup
-------------------------------------
     1k | 1.234s |   0.241s |    5.12
     2k | 4.480s |   0.262s |   17.09
    20k |  7m25s |   0.987s |  450.86

similarly, an /access/ticket request such as the one happening on login goes
down from 4.27s to 109ms with 2k entries (testing with 20k entries fails
because the request times out after 30s, but with the patch it takes 336ms).

the underlying issue is that these two code paths not only iterate over *all
defined ACL paths* to get a complete picture of a user's/token's privileges,
but the fact that that ACL computation for each checked path itself did another
such loop in PVE::AccessControl::roles().

it is enough to iterate over the to-be-checked ACL path in a component-wise
fashion in order to handle role propagation, e.g., when looking at /a/b/c/d,
iterate over

/
/a
/a/b
/a/b/c
/a/b/c/d

in turn instead of all defined ACL paths.

Signed-off-by: Fabian Grünbichler <f.gruenbichler@proxmox.com>
src/PVE/API2/ACL.pm
src/PVE/AccessControl.pm
src/PVE/RPCEnvironment.pm
src/test/parser_writer.pl
src/test/realm_sync_test.pl