#
# 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
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)
)
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
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)
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);
$$;
# 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,
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,
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
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;"
projects / arvados.git / blobdiff