Index: openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions-tediously-explained.xml =================================================================== RCS file: /usr/local/cvsroot/openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions-tediously-explained.xml,v diff -u --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions-tediously-explained.xml 22 Sep 2002 01:01:52 -0000 1.1 @@ -0,0 +1,1394 @@ + + OpenACS 4.x Permissions Tediously Explained + + by Vadim Nasardinov. Modified and converted to Docbook XML by Roberto Mello + + + + + Overview + + The general permissions system has a relatively complex data model in OpenACS 4.x. + Developers who haven't had the time to learn the internals of the data model + may end up writing seemingly correct code that crashes their system in + weird ways. This writeup is the result of my running into such a piece + of code and trying to understand exactly what went wrong. + It is geared towards developers who understand the general permissions + system to the extent that is described in the + + OpenACS 4.x Permisisons documentation, + but who haven't had the opportunity to take a long, careful look at the + system internals. + + + + In OpenACS 4.x, most of the interesting tables are expected to extend (subtype) + the acs_objects table, i.e. they are expected to have an integer + primary key column that references the object_id column of + acs_objects. + + + +create table acs_objects ( + object_id integer + not null + constraint acs_objects_pk primary key, + object_type + not null + constraint acs_objects_object_type_fk references acs_object_types (object_type), + context_id + constraint acs_objects_context_id_fk references acs_objects(object_id), + security_inherit_p char(1) default 't' + not null, + constraint acs_objects_sec_inherit_p_ck + check (security_inherit_p in ('t', 'f')), + creation_user integer, + creation_date date default sysdate not null, + creation_ip varchar2(50), + last_modified date default sysdate not null, + modifying_user integer, + modifying_ip varchar2(50), + constraint acs_objects_context_object_un + unique (context_id, object_id) disable +); + + + + This means that any interesting entity (object) + in the system has an entry in the acs_objects. This + allows developers to define relationships between any two entities A + and B by defining a relationship between their corresponding entries + in the acs_objects table. One of the applications of this + powerful capability is the general permissions system. + + + + At the heart of the permission system are two tables: acs_privileges + and acs_permissions. + + + + + create table acs_privileges ( + privilege varchar2(100) not null + constraint acs_privileges_pk primary key, + pretty_name varchar2(100), + pretty_plural varchar2(100) + ); + + + + create table acs_permissions ( + object_id + not null + constraint acs_permissions_on_what_id_fk references acs_objects (object_id), + grantee_id + not null + constraint acs_permissions_grantee_id_fk references parties (party_id), + privilege + not null + constraint acs_permissions_priv_fk references acs_privileges (privilege), + constraint acs_permissions_pk + primary key (object_id, grantee_id, privilege) + ); + + + + The acs_privileges table stores + named privileges like read, + write, delete, create, and + admin. The acs_permissions + table stores assertions of the form: + + + + Who (grantee_id) can do what (privilege) + on which object (object_id). + + + + The naive approach to managing system security would be to require application developers + to store permission information explicitly about every object, i.e. if the system has 100,000 and 1,000 users + who have the read privilege on all objects, then we would need to store 100,000,000 + entries of the form: + + + + + + + + + + object_id + grantee_id + privilege + + + + + object_id_1 + user_id_1 + 'read' + + + object_id_1 + user_id_2 + 'read' + + + ... + + + object_id_1 + user_id_n + 'read' + + + object_id_2 + user_id_1 + 'read' + + + object_id_2 + user_id_2 + 'read' + + + ... + + + object_id_2 + user_id_n + 'read' + + + ... + + + ... + + + object_id_m + user_id_1 + 'read' + + + object_id_m + user_id_2 + 'read' + + + ... + + + object_id_m + user_id_n + 'read' + + + +
+ + + Although quite feasible, this approach fails to take advantage of the fact + that objects in the system are commonly organized hierarchally, + and permissions usually follow the hierarchical structure, so that if user + X has the read privilege on object A, she typically + also has the read privilege on all objects attached under A. + + + The general permission system, as implemented in OpenACS 4.x, takes advantage + of the hierarchical organization of objects to unburden developers of the + necessity to explicitly maintain security information for every single + object. There are three kinds of hierarchies involved. + These are discussed in the following sections. + +
+ + + Context Hierarchy + + + Suppose objects A, B, ..., + and F form the following hierarchy. + + + + + + + + + + + A + + object_id=10 + + + + + + B + + object_id=20 + + + + C + + object_id=30 + + + + + + D + + object_id=40 + + + + E + + object_id=50 + + + + F + + object_id=60 + + + + + +
+ + + This can be represented in the + acs_objects table + by the following entries: + + + + + + + + + object_id + context_id + + + + + 20 + 10 + + + 30 + 10 + + + 40 + 20 + + + 50 + 20 + + + 60 + 30 + + + +
+ + + The first entry tells us that object 20 is the descendant of object 10, and + the third entry shows that object 40 is the descendant of object 20. By + running a CONNECT BY query, + we can compute that object 40 is the second-generation descendant of object 10. + With this in mind, if we want to record the fact that user Joe has the read privilege on objects + A, ..., F, we only need to record one entry in the + acs_permissions table. + + + + + + + + + + object + grantee + privilege + + + + + A + Joe + read + + + +
+ + + The fact that Joe can also read B, C, + ..., and F can be derived by ascertaining that these objects + are children of A by traversing the context hierarchy. + As it turns out, hierarchical queries are expensive. As + Rafael Schloming put it so aptly, Oracle can't deal with hierarchies for shit. + + + + One way to solve this problem is to cache a flattened view of the context tree like so: + + + + + + + + + + object + ancestor + n_generations + + + + + A + A + 0 + + + B + B + 0 + + + B + A + 1 + + + C + C + 0 + + + C + A + 1 + + + D + D + 0 + + + D + B + 1 + + + D + A + 2 + + + E + E + 0 + + + E + B + 1 + + + E + A + 2 + + + F + F + 0 + + + F + C + 1 + + + F + A + 2 + + + +
+ + + Note that the number of entries in the flattened view grows exponentially with + respect to the depth of the context tree. For instance, if you have a fully + populated binary tree with a depth of n, then the number of entries + in its flattened view is + + + + 1 + 2*2 + 3*4 + 4*8 + 5*16 + ... + (n+1)*2n = n*2n+1 + 1 + + + Despite its potentially great storage costs, maintaining a + flattened representation of the context tree is exactly what OpenACS 4.x + does. The flattened context tree is stored in the + acs_object_context_index table. + + + + create table acs_object_context_index ( + object_id + not null + constraint acs_obj_context_idx_obj_id_fk references acs_objects(object_id), + ancestor_id + not null + constraint acs_obj_context_idx_anc_id_fk references acs_objects(object_id), + n_generations integer + not null + constraint acs_obj_context_idx_n_gen_ck check (n_generations >= 0), + constraint acs_object_context_index_pk + primary key (object_id, ancestor_id) + ) organization index; + + + + A few things to note about this table are these. Number one, it is + an index-organized + table, which means it is substantially optimized for access by primary key. + Number two, as the above computations suggest, the size of the table + grows polynomially + with respect to the average number of descendants that an object + has, and exponentially + with respect to the depth of the context tree. + + + + The acs_object_context_index is kept in sync with the + acs_objects + table by triggers like this: + + + +create or replace trigger acs_objects_context_id_in_tr +after insert on acs_objects +for each row +begin + insert into acs_object_context_index + (object_id, ancestor_id, n_generations) + values + (:new.object_id, :new.object_id, 0); + + if :new.context_id is not null and :new.security_inherit_p = 't' then + insert into acs_object_context_index + (object_id, ancestor_id, + n_generations) + select + :new.object_id as object_id, ancestor_id, + n_generations + 1 as n_generations + from acs_object_context_index + where object_id = :new.context_id; + elsif :new.object_id != 0 then + -- 0 is the id of the security context root object + insert into acs_object_context_index + (object_id, ancestor_id, n_generations) + values + (:new.object_id, 0, 1); + end if; +end; + + + + One final note about + acs_objects. By setting + an object's security_inherit_p column to 'f', you can stop permissions + from cascading down the context tree. In the following example, Joe does not have + the read permissions on C and F. + + + + + + + + + + + +A +object_id=10 +readable by Joe + + + + + + +B +object_id=20 +readable by Joe + + + + +C +object_id=30 +security_inherit_p = 'f' +not readable by Joe + + + + + + +D +object_id=40 + + + + +E +object_id=50 + + + + +F +object_id=60 +security_inherit_p = 'f' +not readable by Joe + + + + + +
+ +
+ + + Privilege Hierarchy + + + Privileges are also organized hierarchically. In addition to the five main system privileges + defined in the ACS Kernel data model, application developers may define their own. For instance, + the Bboard package defines the following privileges: + + + + + + + + privilege + + + + + create_category + + + create_forum + + + create_message + + + delete_category + + + delete_forum + + + delete_message + + + moderate_forum + + + read_category + + + read_forum + + + read_message + + + write_category + + + write_forum + + + write_message + + + +
+ + + By defining parent-child relationship between privileges, the OpenACS data model + makes it easier for developers to manage permissions. Instead of granting + a user explicit read, write, delete, + and create + privileges on an object, it is sufficient to grant the user the admin + privilege to which the first four privileges are tied. To give + a more detailed example, the Bboard privileges are structured + as follows. + + + + + + + + + + + + + + + + + + + + admin + + + create + delete + read + write + moderate forum + + + create category + create forum + create message + delete category + delete forum + delete message + read category + read forum + read message + write category + write forum + write message + + + +
+ + + The parent-child relationship between privileges is represented in + the acs_privilege_hierarchy table: + + + + + create table acs_privilege_hierarchy ( + privilege + not null + constraint acs_priv_hier_priv_fk references acs_privileges (privilege), + child_privilege + not null + constraint acs_priv_hier_child_priv_fk references acs_privileges (privilege), + constraint acs_privilege_hierarchy_pk + primary key (privilege, child_privilege) + ); + + + + As in the case of the context hierarchy, it is convenient to have a flattened representation + of this hierarchal structure. This is accomplished by defining the following view. + + + + create or replace view acs_privilege_descendant_map + as + select + p1.privilege, + p2.privilege as descendant + from + acs_privileges p1, + acs_privileges p2 + where + p2.privilege in + (select + child_privilege + from + acs_privilege_hierarchy + start with + privilege = p1.privilege + connect by + prior child_privilege = privilege + ) + or p2.privilege = p1.privilege; + + + + As the number of different privileges in the system is expected to be + reasonably small, there is no pressing need to cache the flattened ansector-descendant + view of the privilege hierarchy in a specially maintained table like + it is done in the case of the context hierarchy. + + +
+ + + Party Hierarchy + + + Now for the third hierarchy playing a promiment role in the permission system. The party + data model is set up as follows. + + + + + + + + + + + parties + + + + + + + persons + + + + + groups + + + + + + + users + + + + + +
+ + + create table parties ( + party_id + not null + constraint parties_party_id_fk references acs_objects (object_id) + constraint parties_pk primary key, + email varchar2(100) + constraint parties_email_un unique, + url varchar2(200) + ); + + + + create table persons ( + person_id + not null + constraint persons_person_id_fk references parties (party_id) + constraint persons_pk primary key, + first_names varchar2(100) + not null, + last_name varchar2(100) + not null + ); + + + + create table users ( + user_id + not null + constraint users_user_id_fk references persons (person_id) + constraint users_pk primary key, + password char(40), + -- other attributes + ); + + + + create table groups ( + group_id + not null + constraint groups_group_id_fk references parties (party_id) + constraint groups_pk primary key, + group_name varchar2(100) not null + ); + + + + Recall that the grantee_id column of the + acs_permissions table references + parties.party_id. + This means that you can grant a privilege on an object to a party, person, user, or group. + Groups represent aggregations of parties. The most common scenario that you are likely + to encounter is a group that is a collection of users, although you could also + have collections of persons, groups, parties, or any mix thereof. + + + + Given that the most common use of groups is to partition users, how do you + build groups? One way is to grant membership explicitly. If you have + a group named Pranksters, you can assign membership to Pete, + Poly, and Penelope. The fact that these users are members of the + Pranksters group will be recorded in the + membership_rels and acs_rels tables: + + + + create table acs_rels ( + rel_id + not null + constraint acs_rels_rel_id_fk references acs_objects (object_id) + constraint acs_rels_pk primary key, + rel_type + not null + constraint acs_rels_rel_type_fk references acs_rel_types (rel_type), + object_id_one + not null + constraint acs_object_rels_one_fk references acs_objects (object_id), + object_id_two + not null + constraint acs_object_rels_two_fk references acs_objects (object_id), + constraint acs_object_rels_un + unique (rel_type, object_id_one, object_id_two) + ); + + + + create table membership_rels ( + rel_id + constraint membership_rel_rel_id_fk references acs_rels (rel_id) + constraint membership_rel_rel_id_pk primary key, + -- null means waiting for admin approval + member_state varchar2(20) + constraint membership_rel_mem_ck + check (member_state in ('approved', 'banned', 'rejected', 'deleted')) + ); + + + + The acs_rels + table entries would look like so: + + + + + + + + + + + rel_type + + + object_one + + + object_two + + + + + + + membership_rel + + + Pranksters + + + Pete + + + + + membership_rel + + + Pranksters + + + Poly + + + + + membership_rel + + + Pranksters + + + Penelope + + + + +
+ + + Another way of building up groups is by adding subgroups. Suppose + we define Merry Pranksters and Sad Pranksters as subgroups + of Pranksters. We say that the Pranksters group + is composed of + groups Merry Pranksters and Sad Pranksters. This + information is stored in the acs_rels + and composition_rels tables. + + + +create table composition_rels ( + rel_id + constraint composition_rel_rel_id_fk references acs_rels (rel_id) + constraint composition_rel_rel_id_pk primary key +); + + + + The relevant entries in the + acs_rels look like so. + + + + + + + + + + + rel_type + + + object_one + + + object_two + + + + + + + composition_rel + + + Pranksters + + + Merry Pranksters + + + + + composition_rel + + + Pranksters + + + Sad Pranksters + + + + +
+ + + The composition relationship means that if I add Matt, Mel, and Mary to the + Merry Pranksters, + they should also automatically become members of the Pranksters group. + The situation we are + facing in trying to determine whether or not a user is member of a group is similar to the one + discussed above in the case of the context hierarchy. Groups can form hierarchies with + respect to the composition relationship. The compositon relationship is transitive. If + G1 is a subgroup of G2, and G2 is a subgroup of G3, then + G1 is a subgroup of G3; that is, any member of G1 is also a member + of G3. + + + + Traversing the group composition hierarchy requires running + hierarchical queries, + which are expensive in Oracle. As we saw in the Context Hierarchy section, one way of + reducing the performance hit incurred by hierarchical queries is to cache query results in + a table maintained by triggers. The OpenACS 4.x data model defines two such tables: + + + + create table group_component_index ( + group_id not null + constraint group_comp_index_group_id_fk + references groups (group_id), + component_id not null + constraint group_comp_index_comp_id_fk + references groups (group_id), + rel_id not null + constraint group_comp_index_rel_id_fk + references composition_rels (rel_id), + container_id not null + constraint group_comp_index_cont_id_ck + references groups (group_id), + constraint group_component_index_ck + check (group_id != component_id), + constraint group_component_index_pk + primary key (group_id, component_id, rel_id) + ) organization index; + + + + create table group_member_index ( + group_id + not null + constraint group_member_index_grp_id_fk references groups (group_id), + member_id + not null + constraint group_member_index_mem_id_fk references parties (party_id), + rel_id + not null + constraint group_member_index_rel_id_fk references membership_rels (rel_id), + container_id + not null + constraint group_member_index_cont_id_fk references groups (group_id), + constraint group_member_index_pk + primary key (member_id, group_id, rel_id) + ) organization index; + + + + The group_component_index table stores a flattened representation of the + group composition hierarchy that is maintained in sync with the acs_rels + and composition_rels tables through triggers. + + + + As far as the group_member_index table goes, I am not sure I understand its + purpose. It maintains group-member relationships that are resolved with respect + to group composition. Note that information stored in + group_member_index can be trivially derived by joining + membership_rels, + acs_rels, + and group_component_index. Here + is a view that does it. (This view is not part of the OpenACS Kernel data model.) + + + +create or replace view group_member_view +as +select + gci.group_id, r.object_id_two as member_id +from + ( + select + group_id, group_id as component_id + from + groups + union + select + group_id, component_id + from + group_component_index + ) gci, + membership_rels mr, + acs_rels r +where + mr.rel_id = r.rel_id + and r.object_id_one = gci.component_id; + + + + A heuristic way to verify that group_member_view is essentially identical + to group_member_index is to compute the + symmetric difference between the two: + + + +select + group_id, member_id +from + ( + select group_id, member_id from group_member_view + minus + select group_id, member_id from group_member_index + ) +union +select + group_id, member_id +from + ( + select group_id, member_id from group_member_index + minus + select group_id, member_id from group_member_view + ) + + + + The query returns no rows. The important point is, if we + have a flattened view of the composition hierarchy -- like one provided + by the group_component_index table -- + membership relationship resolution can be computed trivially with no hierarchical + queries involved. There is no need to keep the view in a denormalized + table, unless doing so results in substantial performance gains. + + +
+ + + Putting It All Together + + + Security information is queried by calling the acs_permission.permission_p + function in OpenACS 4.x. + + + + create or replace package body acs_permission + as + -- some stuff removed for the sake of brevity + + function permission_p ( + object_id acs_objects.object_id%TYPE, + party_id parties.party_id%TYPE, + privilege acs_privileges.privilege%TYPE + ) return char + as + exists_p char(1); + begin + -- XXX This must be fixed: -1 shouldn't be hardcoded (it is the public) + select decode(count(*),0,'f','t') into exists_p + from acs_object_party_privilege_map + where object_id = permission_p.object_id + and party_id in (permission_p.party_id, -1) + and privilege = permission_p.privilege; + return exists_p; + end; + + end acs_permission; + + + + The function simply queries + acs_object_party_privilege_map, + which is a humongous view that joins three flattened hierarchies: + the context tree, the privilege hierarchy, + the party composition (and membership) hierarchy. As such, + it contains an extremely large number of rows. About + the only kind of query you can run against it is the one + performed by the acs_permission.permission_p + function. Anything other than that would take forever to + finish or would ultimately result in an Oracle error. + + + + For example, do not try to do things like + + + +select count(*) + from acs_object_party_privilege_map; + + + + To give another example of things to avoid, I have seen code like this: + + + + declare + cursor cur is + select + object_id, party_id + from + acs_object_party_privilege_map + where + privilege = 'foo_create'; + begin + -- revoke all 'foo_create' permissions + for rec in cur + loop + acs_permission.revoke_permission ( + object_id => rec.object_id, + grantee_id => rec.party_id, + privilege => 'foo_create' + ); + end loop; + + acs_privilege.remove_child('admin','foo_create'); + acs_privilege.drop_privilege('foo'); + + end; + / + + + + The acs_permission.revoke_permission function merely runs a + delete statement like so: + + + + delete from + acs_permissions + where + object_id = revoke_permission.object_id + and grantee_id = revoke_permission.grantee_id + and privilege = revoke_permission.privilege; + + + + Note that in the above example, acs_permissions had only + one entry that needed to be deleted: + + + + + + + + + + + object_id + + + grantee_id + + + privilege + + + + + + + default_context + + + registered_users + + + foo_create + + + + +
+ + + The above script would never get around to deleting this entry because it had + to loop through a gazillion rows in the humongous + acs_object_party_privilege_map view. + + +
+ + + Appendix: Various View Definitions + + +create or replace view acs_object_party_privilege_map +as +select + ogpm.object_id, + gmm.member_id as party_id, + ogpm.privilege +from + acs_object_grantee_priv_map ogpm, + group_member_map gmm +where + ogpm.grantee_id = gmm.group_id +union +select + object_id, + grantee_id as party_id, + privilege +from + acs_object_grantee_priv_map; + + + +create or replace view acs_object_grantee_priv_map +as +select + a.object_id, + a.grantee_id, + m.descendant as privilege +from + acs_permissions_all a, + acs_privilege_descendant_map m +where + a.privilege = m.privilege; + + + + +create or replace view acs_permissions_all +as +select + op.object_id, + p.grantee_id, + p.privilege +from + acs_object_paths op, + acs_permissions p +where + op.ancestor_id = p.object_id; + + + +create or replace view acs_object_paths +as +select + object_id, + ancestor_id, + n_generations +from + acs_object_context_index; + + + + +create or replace view group_member_map +as +select + group_id, + member_id, + rel_id, + container_id +from + group_member_index; + + + +
+ Index: openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions.xml =================================================================== RCS file: /usr/local/cvsroot/openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions.xml,v diff -u -r1.5 -r1.6 --- openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions.xml 10 Aug 2002 19:45:14 -0000 1.5 +++ openacs-4/packages/acs-core-docs/www/xml/developers-guide/permissions.xml 22 Sep 2002 01:01:52 -0000 1.6 @@ -160,6 +160,11 @@ Permissions + + NOTE: Much more detailed information about the permissions system + and how to use it is available in the + document. + The permissions data model is actually pretty simple. The data model