X-Git-Url: https://git.arvados.org/arvados.git/blobdiff_plain/74be9180943834aebba7683418b4c9700ef16192..b612ef0640ea45f03ad43ed4b124be1034d21071:/services/api/db/migrate/20200501150153_permission_table.rb diff --git a/services/api/db/migrate/20200501150153_permission_table.rb b/services/api/db/migrate/20200501150153_permission_table.rb index d62141a767..0031bd766c 100644 --- a/services/api/db/migrate/20200501150153_permission_table.rb +++ b/services/api/db/migrate/20200501150153_permission_table.rb @@ -2,6 +2,8 @@ # # SPDX-License-Identifier: AGPL-3.0 +require '20200501150153_permission_table_constants' + class PermissionTable < ActiveRecord::Migration[5.0] def up # This is a major migration. We are replacing the @@ -30,22 +32,21 @@ class PermissionTable < ActiveRecord::Migration[5.0] end add_index :trashed_groups, :group_uuid, :unique => true - # - # Starting from a project, recursively traverse all the projects - # underneath it and return a set of project uuids and trash_at - # times (may be null). The initial trash_at can be a timestamp or - # null. The trash_at time propagates downward to groups it owns, - # i.e. when a group is trashed, everything underneath it in the - # ownership hierarchy is also considered trashed. However, this - # is fact is recorded in the trashed_groups table, not by updating - # trash_at field in the groups table. - # ActiveRecord::Base.connection.execute %{ create or replace function project_subtree_with_trash_at (starting_uuid varchar(27), starting_trash_at timestamp) returns table (target_uuid varchar(27), trash_at timestamp) STABLE language SQL as $$ +/* Starting from a project, recursively traverse all the projects + underneath it and return a set of project uuids and trash_at times + (may be null). The initial trash_at can be a timestamp or null. + The trash_at time propagates downward to groups it owns, i.e. when a + group is trashed, everything underneath it in the ownership + hierarchy is also considered trashed. However, this is fact is + recorded in the trashed_groups table, not by updating trash_at field + in the groups table. +*/ WITH RECURSIVE project_subtree(uuid, trash_at) as ( values (starting_uuid, starting_trash_at) @@ -55,28 +56,12 @@ WITH RECURSIVE ) select uuid, trash_at from project_subtree; $$; -} - - # Helper function to populate trashed_groups table. This starts - # with each group owned by a user and computes the subtree under - # that group to find any groups that are trashed. - ActiveRecord::Base.connection.execute %{ -create or replace function compute_trashed () -returns table (uuid varchar(27), trash_at timestamp) -STABLE -language SQL -as $$ -select ps.target_uuid as group_uuid, ps.trash_at from groups, - lateral project_subtree_with_trash_at(groups.uuid, groups.trash_at) ps - where groups.owner_uuid like '_____-tpzed-_______________' -$$; } # Now populate the table. For a non-test databse this is the only # time this ever happens, after this the trash table is updated # incrementally. See app/models/group.rb#update_trash - ActiveRecord::Base.connection.execute("INSERT INTO trashed_groups select * from compute_trashed()") - + refresh_trashed # The table to store the flattened permissions. This is almost # exactly the same as the old materalized_permission_view except @@ -96,10 +81,6 @@ $$; add_index :materialized_permissions, [:user_uuid, :target_uuid], unique: true, name: 'permission_user_target' add_index :materialized_permissions, [:target_uuid], unique: false, name: 'permission_target' - # Helper function. Determines if permission on an object implies - # transitive permission to things the object owns. This is always - # true for groups, but only true for users when the permission - # level is can_manage. ActiveRecord::Base.connection.execute %{ create or replace function should_traverse_owned (starting_uuid varchar(27), starting_perm integer) @@ -107,6 +88,11 @@ create or replace function should_traverse_owned (starting_uuid varchar(27), IMMUTABLE language SQL as $$ +/* Helper function. Determines if permission on an object implies + transitive permission to things the object owns. This is always + true for groups, but only true for users when the permission level + is can_manage. +*/ select starting_uuid like '_____-j7d0g-_______________' or (starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3); $$; @@ -114,17 +100,22 @@ $$; # Merge all permission relationships into a single view. This # consists of: groups (projects) owning things, users owning - # things, and explicit permission links. + # things, users owning themselves, and explicit permission links. # - # Fun fact, a SQL view gets inlined into the query where it is - # used, this enables the query planner to inject constraints, so - # when using the view we only look up edges we plan to traverse - # and avoid a brute force computation of all edges. + # A SQL view gets inlined into the query where it is used as a + # subquery. This enables the query planner to inject constraints, + # so we only look up edges we plan to traverse and avoid a brute + # force query of all edges. ActiveRecord::Base.connection.execute %{ create view permission_graph_edges as - select groups.owner_uuid as tail_uuid, groups.uuid as head_uuid, (3) as val from groups + select groups.owner_uuid as tail_uuid, groups.uuid as head_uuid, + (3) as val, groups.uuid as edge_id from groups union all - select users.owner_uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users + select users.owner_uuid as tail_uuid, users.uuid as head_uuid, + (3) as val, users.uuid as edge_id from users +union all + select users.uuid as tail_uuid, users.uuid as head_uuid, + (3) as val, '' as edge_id from users union all select links.tail_uuid, links.head_uuid, @@ -133,144 +124,135 @@ union all WHEN links.name = 'can_login' THEN 1 WHEN links.name = 'can_write' THEN 2 WHEN links.name = 'can_manage' THEN 3 - END as val + ELSE 0 + END as val, + links.uuid as edge_id from links where links.link_class='permission' } - # From starting_uuid, perform a recursive self-join on the edges - # to follow chains of permissions. This is a breadth-first search - # of the permission graph. Permission is propagated across edges, - # which may narrow the permission for subsequent links (eg I start - # at can_manage but when traversing a can_read link everything - # touched through that link will only be can_read). - # - # Yields the set of objects that are potentially affected, and - # their permission levels granted by having starting_perm on - # starting_uuid. - # - # If starting_uuid is a user, this computes the entire set of - # permissions for that user (because it returns everything that is - # reachable by that user). - # - # Used by compute_permission_subgraph below. - ActiveRecord::Base.connection.execute %{ -create or replace function search_permission_graph (starting_uuid varchar(27), - starting_perm integer) - returns table (target_uuid varchar(27), val integer, traverse_owned bool) -STABLE -language SQL -as $$ -WITH RECURSIVE - traverse_graph(target_uuid, val, traverse_owned) as ( - values (starting_uuid, starting_perm, - should_traverse_owned(starting_uuid, starting_perm)) - union - (select edges.head_uuid, - least(edges.val, traverse_graph.val, - case traverse_graph.traverse_owned - when true then null - else 0 - end), - should_traverse_owned(edges.head_uuid, edges.val) - from permission_graph_edges as edges, traverse_graph - where traverse_graph.target_uuid = edges.tail_uuid)) - select target_uuid, max(val), bool_or(traverse_owned) from traverse_graph - group by (target_uuid); -$$; + # Code fragment that is used below. This is used to ensure that + # the permission edge passed into compute_permission_subgraph + # takes precedence over an existing edge in the "edges" view. + edge_perm = %{ +case (edges.edge_id = perm_edge_id) + when true then starting_perm + else edges.val + end } - # This is the key function. - # - # perm_origin_uuid: The object that 'gets' or 'has' the permission. - # - # starting_uuid: The starting object the permission applies to. - # - # starting_perm: The permission that perm_origin_uuid 'has' on starting_uuid - # One of 1, 2, 3 for can_read, can_write, can_manage - # respectively, or 0 to revoke permissions. - # - # This function is broken up into a number of phases. - # - # 1. perm_from_start: Gets the initial set of objects potentially - # affected by the permission change, using - # search_permission_graph. - # - # 2. additional_perms: Finds other inbound edges that grant - # permissions on the objects in perm_from_start, and computes - # permissions that originate from those. This is required to - # handle the case where there is more than one path through which - # a user gets permission to an object. For example, a user owns a - # project and also shares it can_read with a group the user - # belongs to, adding the can_read link must not overwrite the - # existing can_manage permission granted by ownership. - # - # 3. partial_perms: Combine the permissions computed in the first two phases. - # - # 4. user_identity_perms: If there are any users in the set of - # potentially affected objects and the user's owner was not - # traversed, recompute permissions for that user. This is - # required because users always have permission to themselves - # (identity property) which would be missing from the permission - # set if the user was traversed while computing permissions for - # another object. - # - # 5. all_perms: Combines perm_from_start, additional_perms, and user_identity_perms. - # - # 6. The actual query that produces rows to be added or removed - # from the materialized_permissions table. This is the clever - # bit. - # - # Key insight: because permissions are transitive (unless - # traverse_owned is false), by knowing the permissions granted - # from all the "origins" (perm_origin_uuid, tail_uuid of links - # where head_uuid is in our potentially affected set, etc) we can - # join with the materialized_permissions table to get user - # permissions on those origins, and apply that to the whole graph - # of objects reached through that origin. # + # The primary function to compute permissions for a subgraph. + # This originally was organized somewhat more cleanly, but this + # ran into performance issues due to the query optimizer not + # working across function and "with" expression boundaries. So I + # had to fall back on using string templates for the repeated + # code. I'm sorry. + ActiveRecord::Base.connection.execute %{ create or replace function compute_permission_subgraph (perm_origin_uuid varchar(27), starting_uuid varchar(27), - starting_perm integer) + starting_perm integer, + perm_edge_id varchar(27)) returns table (user_uuid varchar(27), target_uuid varchar(27), val integer, traverse_owned bool) STABLE language SQL as $$ + +/* The purpose of this function is to compute the permissions for a + subgraph of the database, starting from a given edge. The newly + computed permissions are used to add and remove rows from the main + permissions table. + + perm_origin_uuid: The object that 'gets' the permission. + + starting_uuid: The starting object the permission applies to. + + starting_perm: The permission that perm_origin_uuid 'has' on + starting_uuid One of 1, 2, 3 for can_read, + can_write, can_manage respectively, or 0 to revoke + permissions. +*/ with + /* Starting from starting_uuid, determine the set of objects that + could be affected by this permission change. + + Note: We don't traverse users unless it is an "identity" + permission (permission origin is self). + */ perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as ( - select perm_origin_uuid, target_uuid, val, traverse_owned - from search_permission_graph(starting_uuid, starting_perm)), + #{PERM_QUERY_TEMPLATE % {:base_case => %{ + values (perm_origin_uuid, starting_uuid, starting_perm, + should_traverse_owned(starting_uuid, starting_perm), + (perm_origin_uuid = starting_uuid or starting_uuid not like '_____-tpzed-_______________')) +}, +:edge_perm => edge_perm +} }), + + /* Find other inbound edges that grant permissions to 'targets' in + perm_from_start, and compute permissions that originate from + those. + This is necessary for two reasons: + + 1) Other users may have access to a subset of the objects + through other permission links than the one we started from. + If we don't recompute them, their permission will get dropped. + + 2) There may be more than one path through which a user gets + permission to an object. For example, a user owns a project + and also shares it can_read with a group the user belongs + to. adding the can_read link must not overwrite the existing + can_manage permission granted by ownership. + */ additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as ( - select edges.tail_uuid as perm_origin_uuid, ps.target_uuid, ps.val, - should_traverse_owned(ps.target_uuid, ps.val) - from permission_graph_edges as edges, lateral search_permission_graph(edges.head_uuid, edges.val) as ps - where (not (edges.tail_uuid = perm_origin_uuid and - edges.head_uuid = starting_uuid)) and - edges.tail_uuid not in (select target_uuid from perm_from_start) and - edges.head_uuid in (select target_uuid from perm_from_start)), - - partial_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as ( + #{PERM_QUERY_TEMPLATE % {:base_case => %{ + select edges.tail_uuid as origin_uuid, edges.head_uuid as target_uuid, edges.val, + should_traverse_owned(edges.head_uuid, edges.val), + edges.head_uuid like '_____-j7d0g-_______________' + from permission_graph_edges as edges + where edges.edge_id != perm_edge_id and + edges.tail_uuid not in (select target_uuid from perm_from_start where target_uuid like '_____-j7d0g-_______________') and + edges.head_uuid in (select target_uuid from perm_from_start) +}, +:edge_perm => edge_perm +} }), + + /* Combine the permissions computed in the first two phases. */ + all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as ( select * from perm_from_start union all select * from additional_perms - ), + ) - user_identity_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as ( - select users.uuid as perm_origin_uuid, ps.target_uuid, ps.val, ps.traverse_owned - from users, lateral search_permission_graph(users.uuid, 3) as ps - where (users.owner_uuid not in (select target_uuid from partial_perms) or - users.owner_uuid = users.uuid) and - users.uuid in (select target_uuid from partial_perms) - ), + /* The actual query that produces rows to be added or removed + from the materialized_permissions table. This is the clever + bit. - all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as ( - select * from partial_perms - union - select * from user_identity_perms - ) + Key insights: + + * For every group, the materialized_permissions lists all users + that can access to that group. + + * The all_perms subquery has computed permissions on on a set of + objects for all inbound "origins", which are users or groups. + + * Permissions through groups are transitive. + We can infer: + + 1) The materialized_permissions table declares that user X has permission N on group Y + 2) The all_perms result has determined group Y has permission M on object Z + 3) Therefore, user X has permission min(N, M) on object Z + + This allows us to efficiently determine the set of users that + have permissions on the subset of objects, without having to + follow the chain of permission back up to find those users. + + In addition, because users always have permission on themselves, this + query also makes sure those permission rows are always + returned. + */ select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from (select m.user_uuid, u.target_uuid, @@ -278,19 +260,20 @@ with u.traverse_owned from all_perms as u, materialized_permissions as m where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned + AND (m.user_uuid = m.target_uuid or m.target_uuid not like '_____-tpzed-_______________') union all - select perm_origin_uuid as user_uuid, target_uuid, val as perm_level, traverse_owned + select target_uuid as user_uuid, target_uuid, 3, true from all_perms - where all_perms.perm_origin_uuid like '_____-tpzed-_______________') as v + where all_perms.target_uuid like '_____-tpzed-_______________') as v group by v.user_uuid, v.target_uuid $$; } - ActiveRecord::Base.connection.execute %{ -INSERT INTO materialized_permissions -select users.uuid, g.target_uuid, g.val, g.traverse_owned -from users, lateral search_permission_graph(users.uuid, 3) as g where g.val > 0 -} + # + # Populate materialized_permissions by traversing permissions + # starting at each user. + # + refresh_permissions end def down @@ -298,9 +281,7 @@ from users, lateral search_permission_graph(users.uuid, 3) as g where g.val > 0 drop_table :trashed_groups ActiveRecord::Base.connection.execute "DROP function project_subtree_with_trash_at (varchar, timestamp);" - ActiveRecord::Base.connection.execute "DROP function compute_trashed ();" - ActiveRecord::Base.connection.execute "DROP function search_permission_graph(varchar, integer);" - ActiveRecord::Base.connection.execute "DROP function compute_permission_subgraph (varchar, varchar, integer);" + ActiveRecord::Base.connection.execute "DROP function compute_permission_subgraph (varchar, varchar, integer, varchar);" ActiveRecord::Base.connection.execute "DROP function should_traverse_owned(varchar, integer);" ActiveRecord::Base.connection.execute "DROP view permission_graph_edges;"