# --- BEGIN COPYRIGHT BLOCK --- # Copyright (C) 2016 Red Hat, Inc. # All rights reserved. # # License: GPL (version 3 or any later version). # See LICENSE for details. # --- END COPYRIGHT BLOCK --- # # # This test is a bit different to our normal Dirsrv tests. This does not test # DS, but tests the reference implementation of memberOf designed by wibrown # and tbordaz. # # Please see: http://www.port389.org/docs/389ds/design/memberof-scalability.html # # The key idea of this design is that when we have a set of nested groups, # the membershif of A -- member -> B, is reflected in A's memberOf field. # Provided the set of operations proceeding are valid and correct, the memberOf # field of A can be transposed to it's members. IE # # C -- member -> A, no need to read B. C just add's memberOf A, and memberOf B # discovered from A. # # import pytest class MoGroup(object): def __init__(self, name, db): self.name = name self.member = set() self.member_of = set() self.db = db def __str__(self): return self.name def __unicode__(self): return self.name def __repr__(self): return self.name def add_member(self, new_member): # First, we add this member to our group of members. print("==> starting add_member for %s" % self) print(" adding member %s to group %s" % (new_member, self)) self.member.add(new_member) # Now "trigger the post op". We trigger it on the new_member, not ourselves! self.db.update_memberof([new_member,]) print("<== add_member ended") def rename_member(self): pass # We can't actually simulate this in python. But it's easy anyway: # Because a modrdn is source_dn -> target_dn, we can just do: # search '(memberOf=source_dn)', then replace that value with target_dn # on all the objects. Done! No recompute needed :) def delete_member(self, rem_member): # In DS there are actually two cases here. # Here, we are simulating the removal of the memberShip between group X and Y. # In DS this would be a MODIFY operation on a group to MOD_DELETE / MOD_REPLACE the membership. # for a true ldap DELETE operation, similar to rename, we can just do a mod_delete on anything # that contains (memberOf=cn=deleted_thing) print("==> starting delete_member for %s" % self) print(" removing member %s from group %s" % (rem_member, self)) self.member.remove(rem_member) # Now "trigger the post op" self.db.update_memberof([rem_member,]) print("<== delete_member ended") def replace_member(self, to_add_member, to_rem_member): # This is meant to simulate a MODIFY where MOD_ADD and MOD_DELETE happens in the ONE operation. # The reason this is different to add and delete member, is that those happen in individual # atomic actions. This happens at the *same time*, so memberOf has to be able to resolve it # efficiently. # # Now, a naive approach is to treat this as a delete, followed by an add, but then we touch # every node twice to achieve it. # Instead, we just do it as one operation, then run the update_memberof, which resolves both! print("==> starting replace_member for %s" % self) print(" adding %s to %s" % (to_add_member, self)) print(" removing %s from %s" % (to_rem_member, self)) self.member.remove(to_rem_member) self.member.add(to_add_member) # Now "trigger the post op" self.db.update_memberof([to_rem_member, to_add_member]) print("<== replace_member ended") class MoDb(object): # Pretend to be a directory server! # We allow filtering, and retrieval of groups. def __init__(self): self.groups = [] def create_group(self, name): new_group = MoGroup(name, self) self.groups.append(new_group) return new_group def search_group_memberships(self, group): """ This is the equivalent to ldapsearch '(member=cn= ... self)' Find everything that GROUP is a member-of! """ results = [] for g in self.groups: if group in g.member and g not in results: results.append(g) return results def search_group_members(self, group): """ This is the equivalent to ldapsearch '(|(member=cn=....)(...))' For the group, we find and return an array of it's member groups. Depending on how this is done in DS, it may already be in memory if we retrieved the object. """ return group.member def update_memberof(self, modified_groups): """ This represents the algorithm for how memberof will actually work. When a group is modified, it will trigger this statement. This is basically the post op. For this, we take a list of groups that changed in the operation, but for this example, it's only going to be one. This is the first variant, which does not maintain a processed list. """ # These counters are reset between invocations, allows us to show # the number of operations "in theory". operation_count = 0 search_count = 0 # We could do this with recursion, but it's easier with a processing list. unprocessed = [] # First, we have a list of modified groups. We now initiate the unprocessed list # We need to update the groups that were modified to correct their memberOf attrs. for group in modified_groups: if group not in unprocessed: unprocessed.append(group) # We now have a list of groups to fix up :) while len(unprocessed) > 0: # Grab our target group. tgroup = unprocessed.pop() operation_count += 1 print(" --> updating memberof for %s" % tgroup) # We create a working "member of set" working_member_of = set() # First, find who tgroup is a member of. search_count += 1 memberships = self.search_group_memberships(tgroup) # Push them to the working set for membership in memberships: if membership not in working_member_of: working_member_of.add(membership) # Now for each of those memberships, get their member_of lists parent_memberofs = membership.member_of # In DS we would already have this from the previous search, so # no extra cost yet ... # We inherit this from the parent, so push it to our set. for parent_memberof in parent_memberofs: if parent_memberof not in working_member_of: working_member_of.add(parent_memberof) # Now we have a "tentative" memberof set. # This statement is key. It means if we don't update our member_of, we don't need to trigger our # update, nor the updates of any child members! This is what terminates any recursion from occuring, # once we reach a stable state. It also means that with SUPER WEIRD paths through the tree, we will # ALWAYS find a stable, and correct state. # print(" current %s.memberof %s" % (tgroup, tgroup.member_of)) print(" ==== proposed %s.memberof %s" % (tgroup,working_member_of)) if tgroup.member_of != working_member_of: print(" The current memberof set is not correct!") # Update the tgroup member_of set to be the proposed one. In python # we do a simple replace, but in DS, this would probably be some other form of action to # diff the sets. tgroup.member_of = working_member_of # # NOTE: In a recursive case this WILL add a group to be a memberOf itself! # this isn't a bug, it means we've correctly resolved the path through the three to our node. # and accurately reflects, that yes, I am indeed a memberOf myself. # When the recursive link is removed it should be removed! # # Now, because we have changed OUR memberof list, we must tell our members to update, because # theirs is now likely invalid also! search_count += 1 # This isn't really a search in python, but for DS it would be. print(" search_group_members(%s) = %s" % (tgroup, self.search_group_members(tgroup))) for member in self.search_group_members(tgroup): if member not in unprocessed: print(" adding member %s for update..." % member) unprocessed.append(member) else: print(" member of information is unchanged! Operation complete ...") print(" update memberof complete, operation_count = %s, search_count = %s" % (operation_count, search_count)) def fixup_task(self): """ This will go through everything in the tree and fix them all up. There is no start point defined. Consider the fixup task is actually fixup subtree, but with a filter of *. """ self.fixup_subtree(self.groups) def fixup_subtree(self, yet_to_fix): """ In this, we are fixing up part of the tree. For this, we take a group set as the "start point", but in the real DS code this would be a filter. From that start point, we descend to find the leaves of the tree, which is either the group that only contains members (does not belong to another group) or is a """ operation_count = 0 search_count = 0 print("==> starting fixup subtree") # The leaves we are going to look at. leaves = [] # Need to copy here, as yet_to_fix may be a ref to self.groups unprocessed = [] for n in yet_to_fix: unprocessed.append(n) processed = [] # From our group, we could be group B at say: # # A --> B --> C --> D --> E # # For the fix up to work we descend to E, then we trigger a memberof # Update on D! This will naturally begin to work backup the tree! # # The hardest part is recursion. We need to detect we are in a loop # and prevent looking further into it, while declaring this node as # "the leaf". while len(unprocessed) > 0: operation_count += 1 working_group = unprocessed.pop() print(" working_group is %s" % working_group) search_count += 1 group_memberships = self.search_group_memberships(working_group) print(" we belong to %s" % group_memberships ) if len(group_memberships) == 0 or working_group in processed: # This means we are a leaf! if working_group not in leaves: leaves.append(working_group) # Add nothing else to the unprocessed group, we are done here! else: # We are an intermediate, keep going! for g in group_memberships: # This is important, as it prevents recursion. if g not in processed and g not in unprocessed: unprocessed.append(g) # Say we have already been here! processed.append(working_group) ## Right! We've found all all leaves that match our group we want to eventually # fix up. Trigger the fixes! print(" found graph leaves %s" % leaves) # We trigger the fixes not on the leaves, but on the "members" of the leaves. # So from out leaves, find all their members, and make this the set of nodes # to send to update memberof. members_to_fix = [] for leaf in leaves: search_count += 1 for g in self.search_group_members(leaf): if g not in members_to_fix: members_to_fix.append(g) # This actually triggers the fixup! self.update_memberof(members_to_fix) print(" fixup complete, operation_count = %s, search_count = %s" %( operation_count, search_count)) print("<== fixup subtree ended") ### Add cases def test_multipath(): """ This is similar to Thierry's problematic case, but expands on it. We have the following: ---> B ---\ / --> C---\ \ / / v v A -----> D ----> G \ \ ^ ^ \ -----E --/ / ---> F ---/ """ db = MoDb() group_a = db.create_group("a") group_b = db.create_group("b") group_c = db.create_group("c") group_d = db.create_group("d") group_e = db.create_group("e") group_f = db.create_group("f") group_g = db.create_group("g") group_g.add_member(group_b) group_g.add_member(group_c) group_g.add_member(group_d) group_g.add_member(group_e) group_g.add_member(group_f) group_b.add_member(group_a) group_c.add_member(group_a) group_d.add_member(group_a) group_e.add_member(group_a) group_f.add_member(group_a) print("START fixup") group_g.delete_member(group_b) group_g.delete_member(group_c) group_g.delete_member(group_d) group_g.delete_member(group_e) group_g.delete_member(group_f) print("END fixup") assert(group_a.member_of == set([group_b, group_c, group_d, group_e, group_f])) assert(group_b.member_of == set()) assert(group_c.member_of == set()) assert(group_d.member_of == set()) assert(group_e.member_of == set()) assert(group_f.member_of == set()) assert(group_g.member_of == set()) assert False