1 # Copyright (C) The Arvados Authors. All rights reserved.
3 # SPDX-License-Identifier: AGPL-3.0
5 require 'update_permissions'
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 ActiveRecord::Base.connection.execute %{
62 create or replace function compute_trashed ()
63 returns table (uuid varchar(27), trash_at timestamp)
67 /* Helper function to populate trashed_groups table. This starts with
68 each group owned by a user and computes the subtree under that
69 group to find any groups that are trashed.
71 select ps.target_uuid as group_uuid, ps.trash_at from groups,
72 lateral project_subtree_with_trash_at(groups.uuid, groups.trash_at) ps
73 where groups.owner_uuid like '_____-tpzed-_______________'
77 # Now populate the table. For a non-test databse this is the only
78 # time this ever happens, after this the trash table is updated
79 # incrementally. See app/models/group.rb#update_trash
80 ActiveRecord::Base.connection.execute("INSERT INTO trashed_groups select * from compute_trashed()")
82 # The table to store the flattened permissions. This is almost
83 # exactly the same as the old materalized_permission_view except
84 # that the target_owner_uuid colunm in the view is now just a
85 # boolean traverse_owned (the column was only ever tested for null
88 # For details on how this table is used to apply permissions to
89 # queries, see app/models/arvados_model.rb#readable_by
91 create_table :materialized_permissions, :id => false do |t|
95 t.boolean :traverse_owned
97 add_index :materialized_permissions, [:user_uuid, :target_uuid], unique: true, name: 'permission_user_target'
98 add_index :materialized_permissions, [:target_uuid], unique: false, name: 'permission_target'
100 ActiveRecord::Base.connection.execute %{
101 create or replace function should_traverse_owned (starting_uuid varchar(27),
102 starting_perm integer)
107 /* Helper function. Determines if permission on an object implies
108 transitive permission to things the object owns. This is always
109 true for groups, but only true for users when the permission level
112 select starting_uuid like '_____-j7d0g-_______________' or
113 (starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3);
117 # Merge all permission relationships into a single view. This
118 # consists of: groups (projects) owning things, users owning
119 # things, and explicit permission links.
121 # Fun fact, a SQL view gets inlined into the query where it is
122 # used, this enables the query planner to inject constraints, so
123 # when using the view we only look up edges we plan to traverse
124 # and avoid a brute force computation of all edges.
125 ActiveRecord::Base.connection.execute %{
126 create view permission_graph_edges as
127 select groups.owner_uuid as tail_uuid, groups.uuid as head_uuid, (3) as val from groups
129 select users.owner_uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users
131 select users.uuid as tail_uuid, users.uuid as head_uuid, (3) as val from users
133 select links.tail_uuid,
136 WHEN links.name = 'can_read' THEN 1
137 WHEN links.name = 'can_login' THEN 1
138 WHEN links.name = 'can_write' THEN 2
139 WHEN links.name = 'can_manage' THEN 3
143 where links.link_class='permission'
147 case (edges.tail_uuid = perm_origin_uuid AND
148 edges.head_uuid = starting_uuid)
149 when true then starting_perm
154 ActiveRecord::Base.connection.execute %{
155 create or replace function compute_permission_subgraph (perm_origin_uuid varchar(27),
156 starting_uuid varchar(27),
157 starting_perm integer)
158 returns table (user_uuid varchar(27), target_uuid varchar(27), val integer, traverse_owned bool)
162 /* perm_origin_uuid: The object that 'gets' or 'has' the permission.
164 starting_uuid: The starting object the permission applies to.
166 starting_perm: The permission that perm_origin_uuid 'has' on
167 starting_uuid One of 1, 2, 3 for can_read,
168 can_write, can_manage respectively, or 0 to revoke
171 This function is broken up into a number of clauses, described
174 Note on query optimization:
176 Each clause in a "with" statement is called a "common table
179 In Postgres, they are evaluated in sequence and results of each CTE
180 is stored in a temporary table. This means Postgres does not
181 propagate constraints from later subqueries to earlier subqueries
184 This is a problem if, for example, a later subquery chooses 10
185 items out of a set of 1000000 defined by an earlier subquery,
186 because it will always compute all 1000000 rows even if the query
187 on the 1000000 rows could have been constrained. This is why
188 permission_graph_edges is a view -- views are inlined so and can be
189 optimized using external constraints.
191 The query optimizer does sort the temporary tables for later use in
194 Final note, this query would have been almost impossible to write
195 (and certainly impossible to read) without splitting it up using
196 SQL "with" but unfortunately it also stumbles into a frustrating
197 Postgres optimizer bug, see
198 lib/refresh_permission_view.rb#update_permissions
199 for details and a partial workaround.
202 /* Gets the initial set of objects potentially affected by the
203 permission change, using search_permission_graph.
205 perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
206 #{PERM_QUERY_TEMPLATE % {:base_case => %{
207 values (perm_origin_uuid, starting_uuid, starting_perm,
208 should_traverse_owned(starting_uuid, starting_perm),
209 (perm_origin_uuid = starting_uuid or starting_uuid not like '_____-tpzed-_______________'))
211 :override => override
214 /* Finds other inbound edges that grant permissions on the objects
215 in perm_from_start, and computes permissions that originate from
216 those. This is required to handle the case where there is more
217 than one path through which a user gets permission to an object.
218 For example, a user owns a project and also shares it can_read
219 with a group the user belongs to, adding the can_read link must
220 not overwrite the existing can_manage permission granted by
223 additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
224 #{PERM_QUERY_TEMPLATE % {:base_case => %{
225 select edges.tail_uuid as origin_uuid, edges.head_uuid as target_uuid, edges.val,
226 should_traverse_owned(edges.head_uuid, edges.val),
227 edges.head_uuid like '_____-j7d0g-_______________'
228 from permission_graph_edges as edges
229 where (not (edges.tail_uuid = perm_origin_uuid and
230 edges.head_uuid = starting_uuid)) and
231 edges.tail_uuid not in (select target_uuid from perm_from_start where target_uuid like '_____-j7d0g-_______________') and
232 edges.head_uuid in (select target_uuid from perm_from_start)
234 :override => override
237 /* Combines the permissions computed in the first two phases. */
238 all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
239 select * from perm_from_start
241 select * from additional_perms
244 /* The actual query that produces rows to be added or removed
245 from the materialized_permissions table. This is the clever
250 * Permissions are transitive (with some special cases involving
251 users, this is controlled by the traverse_owned flag).
253 * A user object can only gain permissions via an inbound edge,
254 or appearing in the graph.
256 * The materialized_permissions table includes the permission
257 each user has on the tail end of each inbound edge.
259 * The all_perms subquery has permissions for each object in the
260 subgraph reachable from certain origin (tail end of an edge).
262 * Therefore, for each user, we can compute user permissions on
263 each object in subgraph by determining the permission the user
264 has on each origin (tail end of an edge), joining that with the
265 perm_origin_uuid column of all_perms, and taking the least() of
266 the origin edge or all_perms val (because of the "least
267 permission on the path" rule). If an object was reachable by
268 more than one path (appears with more than one origin), we take
269 the max() of the computed permissions.
271 * Finally, because users always have permission on themselves, the
272 query also makes sure those permission rows are always
275 select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
278 least(u.val, m.perm_level) as perm_level,
280 from all_perms as u, materialized_permissions as m
281 where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
282 AND (m.user_uuid = m.target_uuid or m.target_uuid not like '_____-tpzed-_______________')
284 select target_uuid as user_uuid, target_uuid, 3, true
286 where all_perms.target_uuid like '_____-tpzed-_______________') as v
287 group by v.user_uuid, v.target_uuid
292 # Populate the materialized_permissions by traversing permissions
293 # starting at each user.
295 ActiveRecord::Base.connection.execute %{
296 INSERT INTO materialized_permissions
297 #{PERM_QUERY_TEMPLATE % {:base_case => %{
298 select uuid, uuid, 3, true, true from users
306 drop_table :materialized_permissions
307 drop_table :trashed_groups
309 ActiveRecord::Base.connection.execute "DROP function project_subtree_with_trash_at (varchar, timestamp);"
310 ActiveRecord::Base.connection.execute "DROP function compute_trashed ();"
311 ActiveRecord::Base.connection.execute "DROP function compute_permission_subgraph (varchar, varchar, integer);"
312 ActiveRecord::Base.connection.execute "DROP function should_traverse_owned(varchar, integer);"
313 ActiveRecord::Base.connection.execute "DROP view permission_graph_edges;"
315 ActiveRecord::Base.connection.execute(%{
316 CREATE MATERIALIZED VIEW materialized_permission_view AS
317 WITH RECURSIVE perm_value(name, val) AS (
318 VALUES ('can_read'::text,(1)::smallint), ('can_login'::text,1), ('can_write'::text,2), ('can_manage'::text,3)
319 ), perm_edges(tail_uuid, head_uuid, val, follow, trashed) AS (
320 SELECT links.tail_uuid,
323 ((pv.val = 3) OR (groups.uuid IS NOT NULL)) AS follow,
324 (0)::smallint AS trashed,
325 (0)::smallint AS followtrash
327 LEFT JOIN perm_value pv ON ((pv.name = (links.name)::text)))
328 LEFT JOIN public.groups ON (((pv.val < 3) AND ((groups.uuid)::text = (links.head_uuid)::text))))
329 WHERE ((links.link_class)::text = 'permission'::text)
331 SELECT groups.owner_uuid,
336 WHEN ((groups.trash_at IS NOT NULL) AND (groups.trash_at < clock_timestamp())) THEN 1
341 ), perm(val, follow, user_uuid, target_uuid, trashed) AS (
342 SELECT (3)::smallint AS val,
344 (users.uuid)::character varying(32) AS user_uuid,
345 (users.uuid)::character varying(32) AS target_uuid,
346 (0)::smallint AS trashed
349 SELECT (LEAST((perm_1.val)::integer, edges.val))::smallint AS val,
352 (edges.head_uuid)::character varying(32) AS target_uuid,
353 ((GREATEST((perm_1.trashed)::integer, edges.trashed) * edges.followtrash))::smallint AS trashed
355 JOIN perm_edges edges ON ((perm_1.follow AND ((edges.tail_uuid)::text = (perm_1.target_uuid)::text))))
357 SELECT perm.user_uuid,
359 max(perm.val) AS perm_level,
361 WHEN true THEN perm.target_uuid
362 ELSE NULL::character varying
363 END AS target_owner_uuid,
364 max(perm.trashed) AS trashed
366 GROUP BY perm.user_uuid, perm.target_uuid,
368 WHEN true THEN perm.target_uuid
369 ELSE NULL::character varying
375 add_index :materialized_permission_view, [:trashed, :target_uuid], name: 'permission_target_trashed'
376 add_index :materialized_permission_view, [:user_uuid, :trashed, :perm_level], name: 'permission_target_user_trashed_level'
377 create_table :permission_refresh_lock
379 ActiveRecord::Base.connection.execute 'REFRESH MATERIALIZED VIEW materialized_permission_view;'