1 # Copyright (C) The Arvados Authors. All rights reserved.
3 # SPDX-License-Identifier: AGPL-3.0
5 require '20200501150153_permission_table_constants'
7 class PermissionTable < ActiveRecord::Migration[5.0]
9 # This is a major migration. We are replacing the
10 # materialized_permission_view, which is fully recomputed any time
11 # a permission changes (and becomes very expensive as the number
12 # of users/groups becomes large), with a new strategy that only
13 # recomputes permissions for the subset of objects that are
14 # potentially affected by the addition or removal of a permission
15 # relationship (i.e. ownership or a permission link).
17 # This also disentangles the concept of "trashed groups" from the
18 # permissions system. Updating trashed items follows a similar
19 # (but less complicated) strategy to updating permissions, so it
20 # may be helpful to look at that first.
23 ActiveRecord::Base.connection.execute "DROP MATERIALIZED VIEW IF EXISTS materialized_permission_view;"
24 drop_table :permission_refresh_lock
26 # This table stores the set of trashed groups and their trash_at
27 # time. Used to exclude trashed projects and their contents when
28 # getting object listings.
29 create_table :trashed_groups, :id => false do |t|
33 add_index :trashed_groups, :group_uuid, :unique => true
35 ActiveRecord::Base.connection.execute %{
36 create or replace function project_subtree_with_trash_at (starting_uuid varchar(27), starting_trash_at timestamp)
37 returns table (target_uuid varchar(27), trash_at timestamp)
41 /* Starting from a project, recursively traverse all the projects
42 underneath it and return a set of project uuids and trash_at times
43 (may be null). The initial trash_at can be a timestamp or null.
44 The trash_at time propagates downward to groups it owns, i.e. when a
45 group is trashed, everything underneath it in the ownership
46 hierarchy is also considered trashed. However, this is fact is
47 recorded in the trashed_groups table, not by updating trash_at field
51 project_subtree(uuid, trash_at) as (
52 values (starting_uuid, starting_trash_at)
54 select groups.uuid, LEAST(project_subtree.trash_at, groups.trash_at)
55 from groups join project_subtree on (groups.owner_uuid = project_subtree.uuid)
57 select uuid, trash_at from project_subtree;
61 # Now populate the table. For a non-test databse this is the only
62 # time this ever happens, after this the trash table is updated
63 # incrementally. See app/models/group.rb#update_trash
66 # The table to store the flattened permissions. This is almost
67 # exactly the same as the old materalized_permission_view except
68 # that the target_owner_uuid colunm in the view is now just a
69 # boolean traverse_owned (the column was only ever tested for null
72 # For details on how this table is used to apply permissions to
73 # queries, see app/models/arvados_model.rb#readable_by
75 create_table :materialized_permissions, :id => false do |t|
79 t.boolean :traverse_owned
81 add_index :materialized_permissions, [:user_uuid, :target_uuid], unique: true, name: 'permission_user_target'
82 add_index :materialized_permissions, [:target_uuid], unique: false, name: 'permission_target'
84 ActiveRecord::Base.connection.execute %{
85 create or replace function should_traverse_owned (starting_uuid varchar(27),
86 starting_perm integer)
91 /* Helper function. Determines if permission on an object implies
92 transitive permission to things the object owns. This is always
93 true for groups, but only true for users when the permission level
96 select starting_uuid like '_____-j7d0g-_______________' or
97 (starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3);
101 # Merge all permission relationships into a single view. This
102 # consists of: groups (projects) owning things, users owning
103 # things, users owning themselves, and explicit permission links.
105 # A SQL view gets inlined into the query where it is used as a
106 # subquery. This enables the query planner to inject constraints,
107 # so we only look up edges we plan to traverse and avoid a brute
108 # force query of all edges.
109 ActiveRecord::Base.connection.execute %{
110 create view permission_graph_edges as
111 select groups.owner_uuid as tail_uuid, groups.uuid as head_uuid, (3) as val from groups
113 select users.owner_uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users
115 select users.uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users
117 select links.tail_uuid,
120 WHEN links.name = 'can_read' THEN 1
121 WHEN links.name = 'can_login' THEN 1
122 WHEN links.name = 'can_write' THEN 2
123 WHEN links.name = 'can_manage' THEN 3
127 where links.link_class='permission'
130 # Code fragment that is used below. This is used to ensure that
131 # the permission edge passed into compute_permission_subgraph
132 # takes precedence over an existing edge in the "edges" view.
134 case (edges.tail_uuid = perm_origin_uuid AND
135 edges.head_uuid = starting_uuid)
136 when true then starting_perm
142 # The primary function to compute permissions for a subgraph.
143 # This originally was organized somewhat more cleanly, but this
144 # ran into performance issues due to the query optimizer not
145 # working across function and "with" expression boundaries. So I
146 # had to fall back on using string templates for the repeated
149 ActiveRecord::Base.connection.execute %{
150 create or replace function compute_permission_subgraph (perm_origin_uuid varchar(27),
151 starting_uuid varchar(27),
152 starting_perm integer)
153 returns table (user_uuid varchar(27), target_uuid varchar(27), val integer, traverse_owned bool)
158 /* The purpose of this function is to compute the permissions for a
159 subgraph of the database, starting from a given edge. The newly
160 computed permissions are used to add and remove rows from the main
163 perm_origin_uuid: The object that 'gets' the permission.
165 starting_uuid: The starting object the permission applies to.
167 starting_perm: The permission that perm_origin_uuid 'has' on
168 starting_uuid One of 1, 2, 3 for can_read,
169 can_write, can_manage respectively, or 0 to revoke
173 /* Starting from starting_uuid, determine the set of objects that
174 could be affected by this permission change.
176 Note: We don't traverse users unless it is an "identity"
177 permission (permission origin is self).
179 perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
180 #{PERM_QUERY_TEMPLATE % {:base_case => %{
181 values (perm_origin_uuid, starting_uuid, starting_perm,
182 should_traverse_owned(starting_uuid, starting_perm),
183 (perm_origin_uuid = starting_uuid or starting_uuid not like '_____-tpzed-_______________'))
185 :override => override
188 /* Find other inbound edges that grant permissions to 'targets' in
189 perm_from_start, and compute permissions that originate from
192 This is necessary for two reasons:
194 1) Other users may have access to a subset of the objects
195 through other permission links than the one we started from.
196 If we don't recompute them, their permission will get dropped.
198 2) There may be more than one path through which a user gets
199 permission to an object. For example, a user owns a project
200 and also shares it can_read with a group the user belongs
201 to. adding the can_read link must not overwrite the existing
202 can_manage permission granted by ownership.
204 additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
205 #{PERM_QUERY_TEMPLATE % {:base_case => %{
206 select edges.tail_uuid as origin_uuid, edges.head_uuid as target_uuid, edges.val,
207 should_traverse_owned(edges.head_uuid, edges.val),
208 edges.head_uuid like '_____-j7d0g-_______________'
209 from permission_graph_edges as edges
210 where (not (edges.tail_uuid = perm_origin_uuid and
211 edges.head_uuid = starting_uuid)) and
212 edges.tail_uuid not in (select target_uuid from perm_from_start where target_uuid like '_____-j7d0g-_______________') and
213 edges.head_uuid in (select target_uuid from perm_from_start)
215 :override => override
218 /* Combine the permissions computed in the first two phases. */
219 all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
220 select * from perm_from_start
222 select * from additional_perms
225 /* The actual query that produces rows to be added or removed
226 from the materialized_permissions table. This is the clever
231 * For every group, the materialized_permissions lists all users
232 that can access to that group.
234 * The all_perms subquery has computed permissions on on a set of
235 objects for all inbound "origins", which are users or groups.
237 * Permissions through groups are transitive.
241 1) The materialized_permissions table declares that user X has permission N on group Y
242 2) The all_perms result has determined group Y has permission M on object Z
243 3) Therefore, user X has permission min(N, M) on object Z
245 This allows us to efficiently determine the set of users that
246 have permissions on the subset of objects, without having to
247 follow the chain of permission back up to find those users.
249 In addition, because users always have permission on themselves, this
250 query also makes sure those permission rows are always
253 select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
256 least(u.val, m.perm_level) as perm_level,
258 from all_perms as u, materialized_permissions as m
259 where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
260 AND (m.user_uuid = m.target_uuid or m.target_uuid not like '_____-tpzed-_______________')
262 select target_uuid as user_uuid, target_uuid, 3, true
264 where all_perms.target_uuid like '_____-tpzed-_______________') as v
265 group by v.user_uuid, v.target_uuid
270 # Populate materialized_permissions by traversing permissions
271 # starting at each user.
277 drop_table :materialized_permissions
278 drop_table :trashed_groups
280 ActiveRecord::Base.connection.execute "DROP function project_subtree_with_trash_at (varchar, timestamp);"
281 ActiveRecord::Base.connection.execute "DROP function compute_permission_subgraph (varchar, varchar, integer);"
282 ActiveRecord::Base.connection.execute "DROP function should_traverse_owned(varchar, integer);"
283 ActiveRecord::Base.connection.execute "DROP view permission_graph_edges;"
285 ActiveRecord::Base.connection.execute(%{
286 CREATE MATERIALIZED VIEW materialized_permission_view AS
287 WITH RECURSIVE perm_value(name, val) AS (
288 VALUES ('can_read'::text,(1)::smallint), ('can_login'::text,1), ('can_write'::text,2), ('can_manage'::text,3)
289 ), perm_edges(tail_uuid, head_uuid, val, follow, trashed) AS (
290 SELECT links.tail_uuid,
293 ((pv.val = 3) OR (groups.uuid IS NOT NULL)) AS follow,
294 (0)::smallint AS trashed,
295 (0)::smallint AS followtrash
297 LEFT JOIN perm_value pv ON ((pv.name = (links.name)::text)))
298 LEFT JOIN public.groups ON (((pv.val < 3) AND ((groups.uuid)::text = (links.head_uuid)::text))))
299 WHERE ((links.link_class)::text = 'permission'::text)
301 SELECT groups.owner_uuid,
306 WHEN ((groups.trash_at IS NOT NULL) AND (groups.trash_at < clock_timestamp())) THEN 1
311 ), perm(val, follow, user_uuid, target_uuid, trashed) AS (
312 SELECT (3)::smallint AS val,
314 (users.uuid)::character varying(32) AS user_uuid,
315 (users.uuid)::character varying(32) AS target_uuid,
316 (0)::smallint AS trashed
319 SELECT (LEAST((perm_1.val)::integer, edges.val))::smallint AS val,
322 (edges.head_uuid)::character varying(32) AS target_uuid,
323 ((GREATEST((perm_1.trashed)::integer, edges.trashed) * edges.followtrash))::smallint AS trashed
325 JOIN perm_edges edges ON ((perm_1.follow AND ((edges.tail_uuid)::text = (perm_1.target_uuid)::text))))
327 SELECT perm.user_uuid,
329 max(perm.val) AS perm_level,
331 WHEN true THEN perm.target_uuid
332 ELSE NULL::character varying
333 END AS target_owner_uuid,
334 max(perm.trashed) AS trashed
336 GROUP BY perm.user_uuid, perm.target_uuid,
338 WHEN true THEN perm.target_uuid
339 ELSE NULL::character varying
345 add_index :materialized_permission_view, [:trashed, :target_uuid], name: 'permission_target_trashed'
346 add_index :materialized_permission_view, [:user_uuid, :trashed, :perm_level], name: 'permission_target_user_trashed_level'
347 create_table :permission_refresh_lock
349 ActiveRecord::Base.connection.execute 'REFRESH MATERIALIZED VIEW materialized_permission_view;'