Re: Questions: Recursive group lookup

[Arthur de Jong <arthur [at] arthurdejong.org>]

On Sun, 2010-01-31 at 17:42 +0100, Jan Schampera wrote:
> > The only way (to really catch all) I see is to (recursively)
> > getmembers() all known groups, maybe with some less exclusions before,
> > but... That sounds *heavy*. Though I remember some setting in the PADL
> > modules about the initgroup implementation being recursive or not, and
> > the performance loss. It could be that this is the only way.
> 
> I have a rough imagination about a search algo that is a little bit
> optimized.

The problem is that you have three types of lookups:
- get all groups
- search for a group by some criteria (name, gid)
- get groups by member

These currently use basically the same code but maybe it is better to
have three different algorithms. For the second one for instance the
recursion shouldn't bee too much of a problem (no-one is going to nest
groups ten levels deep) but for the first there may be a reason to
optimise (e.g. cache groups so they may be re-used more efficiently when
they are referenced from multiple groups).

The last search really words differently because we are not interested
in the members but only in the group names.

It gets even more complex if you want to allow the second-level groups
not to be posixGroup objects (not unreasonable I think), e.g:

  dn: cn=users,ou=groups,dc=example,dc=com
  objectClass: posixGroup
  objectClass: groupOfUniqueNames
  gidNumber: 100
  memberUid: arthur
  uniqueMember: cn=otherusers,ou=groups,dc=example,dc=com

  dn: cn=otherusers,ou=groups,dc=example,dc=com
  objectClass: groupOfUniqueNames
  uniqueMember: cn=Some User,ou=people,dc=example,dc=com

> Below is the code in TheBonsaiPseudoCode(TM)...
> 
> ITERATE (all posixGroup objects) AS group;
>   IF (groupDN.memberUID == UID)
>     grouplist += group.cn;
>     seenlist += group.dn;
>     next iteration;
>   END IF;
>   IF (group.uniqueMember == DN of UID)
>     grouplist += group.cn;
>     seenlist += group.dn;
>     next iteration;
>   END IF;
>   IF ((group.uniqueMember ==
>        DN of object with (objectClass == posixGroup))
>       && ! (group.uniqueMember in seenlist))
>     memberslist := getmembers of group.uniqueMember;
>     IF (UID in memberslist)
>       grouplist += group.cn;
>       seenlist += group.dn;
>       next iteration;
>     END IF;
>   END IF;
>   seenlist += group.dn;
> END ITERATE;
> 
> The idea is to exclude direct group assignments first, and only go
> deeper when a group is referenced. Also maintain a list of already
> inspected group DNs to not work too much. The part which gets the group
> members doesn't need to be recursive here (it would slow down anyways).

I think I miss a loop over attribute values but keeping a list of
already seen group DNs is indeed necessary.

Another solution for the username -> groups lookup would be to get all
the groups that have the selected user as member and then recursively
gets all the groups that have that group as a member. It is probably
better to have a queue-like mechanism of groups to check to avoid
duplicates. This has the advantage of letting the LDAP server do all the
heavy lifting of searching for entries (it has indexes, etc) but at the
cost of more queries.

For the forward lookup (group -> members) perhaps it is sufficient to
extend the dn2uid() code to be able to return:
  - this is a user, this is the uid
  - this is a DN of a user, this is the uid
  - this is a DN of a group, this is the LDAP entry
  - this is something unknown
and perform caching because the DN of an object is not expected to point
to an object of a different type often. The problem is that we can't
cache the actual LDAP entry because it is freed when the search is
closed and re-used between different threads.

> Any optimization potential here? Something I don't know about LDAP
> searches or so?

I know that there is a possibility to have a memberOf attribute in user
entries and have it automatically populated by the LDAP server but I
don't have any experience in that area. That would make some searches
simpler but on the other hand it may not be an option for all users and
I don't know how nested groups are handled there.

All in all, the group lookups are difficult and you have to be careful
not to do too many queries or otherwise it will be too slow and not to
return or search through duplicate entries.

-- 
-- arthur - arthur@arthurdejong.org - http://arthurdejong.org --

--
To unsubscribe send an email to
nss-pam-ldapd-users-unsubscribe@lists.arthurdejong.org or see
http://lists.arthurdejong.org/nss-pam-ldapd-users